Editorial for Coder Rating


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=300010;
      maxc=100010;
var n:longint;
    a,b,d,re,e:array[1..maxn] of longint;
    f:array[0..maxc] of longint;

procedure sort(l,r:longint);
var x,y,i,j,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (b[j]>y)) do j:=j-1;
           if i<=j then
           begin
                t:=b[i]; b[i]:=b[j]; b[j]:=t;
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=d[i]; d[i]:=d[j]; d[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do
     begin
          read(a[i],b[i]);
          d[i]:=i;
     end;
     SORT(1,N);
     for i:=1 to n do e[d[i]]:=i;
     close(input);
end;

function sum(i:longint):longint;
var t:longint;
begin
     t:=0;
     while i>0 do
     begin
          t:=t+f[i];
          i:=i-i and (-i);
     end;
     sum:=t;
end;

procedure add(i:longint);
begin
     while i<=maxc do
     begin
          f[i]:=f[i]+1;
          i:=i+i and (-i);
     end;
end;


procedure pr;
var i,j:longint;
begin
     for i:=1 to n do
     begin
          if (i>1) and (a[i]=a[i-1]) and (b[i]=b[i-1]) then re[i]:=re[i-1]
          else re[i]:=sum(b[i]);
          add(b[i]);
     end;
end;

procedure wf;
var i:longint;
begin
     assign(output,fo); rewrite(output);
     for i:=1 to n do writeln(re[e[i]]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define MAX 100001 
#define N 300000

struct contestant {
    int p1, p2, id;
    bool operator < (const contestant &o) const {
        return p1 < o.p1 || p1 == o.p1 && p2 < o.p2;
    }
    bool operator == (const contestant &o) const {
        return p1 == o.p1 && p2 == o.p2;
    }
} a[N];
int answer[N], bit[MAX+1], n;

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d",&a[i].p1,&a[i].p2);
        ++a[i].p1; ++a[i].p2; a[i].id = i;
    }
}

void add(int idx, int v) {
    for(; idx <= MAX; idx += idx & -idx) bit[idx] += v;
}

int sum(int idx) {
    int res = 0;
    for(; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

void solve() {
    sort(a, a+n);
    for(int i = 0; i < n; ++i) {
        if(i != 0 && a[i] == a[i-1]) {
            answer[a[i].id] = answer[a[i-1].id];
        } else answer[a[i].id] = sum(a[i].p2);
        add(a[i].p2, 1);
    }
    for(int i = 0; i < n; ++i) printf("%d\n", answer[i]);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

program crate;
uses    math;
type    e=record
        x,y,p:longint;
        end;
const   maxn=300055;
        maxV=100110;
        fi='';
var     a:array[0..maxn] of e;
        res:array[0..maxn] of longint;
        bit:array[0..maxV] of longint;
        n:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                readln(inp,a[i].x,a[i].y);
                //inc(a[i].x);
                //inc(a[i].y);
                a[i].p:=i;
        end;
        close(inp);
end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
        t:e;
begin
        if l>=r then exit;
        t:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].x<t.x) or ((a[i].x=t.x) and (a[i].y<t.y)) do inc(i);
                while (a[j].x>t.x) or ((a[j].x=t.x) and (a[j].y>t.y)) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(l,j);
        sort(i,r);
end;

procedure update(i:longint);
begin
        while i<=maxV do
        begin
                inc(bit[i]);
                i:=i+i and (-i);
        end;
end;

function get(i:longint):longint;
var     sum:longint;
begin
        sum:=0;
        while i>0 do
        begin
                inc(sum,bit[i]);
                i:=i-i and (-i);
        end;
        exit(sum);
end;

procedure process;
var     i,j,k:longint;
begin
        i:=1;
        while i<=n do
        begin
                j:=i;
                while (j<=n) and (a[j].x=a[i].x) and (a[j].y=a[i].y) do inc(j);
                for k:=i to j-1 do
                res[a[k].p]:=get(a[k].y);
                for k:=i to j-1 do
                update(a[k].y);
                i:=j;
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to n do
        writeln(res[i]);
end;

begin
        input;
        sort(1,n);
        process;
        output;
end.

Code mẫu của RR

{$IFDEF debug}
  {$R+,Q+}
  {$Mode objFPC}
{$ELSE}
  {$R-,Q-}
  {$inline on}
{$ENDIF}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       300111;
type
  BITree        =       object
        val     :       array[1..100111] of longint;
        procedure update(u,k:longint);
        function get(u:longint):longint;
  end;

var
  f1,f2         :       text;
  n,maxb        :       longint;
  a,b,ind,better:       array[1..MAXN] of longint;
  bit           :       BITree;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,n); maxb:=-1;
      for i:=1 to n do
        begin
          read(f1,a[i],b[i]);
          maxb:=max(maxb,b[i]);
          ind[i]:=i;
        end;
    end;
procedure swap(var a,b:longint); inline;
    var
      temp:longint;
    begin
      temp:=a; a:=b; b:=temp;
    end;
    var
      ma,mb,key:longint;
procedure sort(l,r:longint); inline;
    var
      i,j:longint;
    begin
      i:=l; j:=r; key:=l+random(r-l+1);
      ma:=a[key]; mb:=b[key];
      repeat
        while (a[i]<ma) or ((a[i]=ma) and (b[i]<mb)) do inc(i);
        while (a[j]>ma) or ((a[j]=ma) and (b[j]>mb)) do dec(j);
        if i<=j then
          begin
            swap(a[i],a[j]);
            swap(b[i],b[j]);
            swap(ind[i],ind[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;
procedure BITree.update(u,k:longint); inline;
    var
      v:longint;
    begin
      inc(val[u],k);
      v:=u+u and (-u);
      if v<=maxb then update(v,k);
    end;
function BITree.get(u:longint):longint; inline;
    var
      v,kq:longint;
    begin
      kq:=val[u];
      v:=u-u and (-u);
      if v>0 then inc(kq,get(v));
      exit(kq);
    end;
procedure solve;
    var
      i,count,last:longint;
    begin
      count:=0; last:=0;
      for i:=1 to n do
        if (a[i]=a[i-1]) and (b[i]=b[i-1]) then
          begin
            better[ind[i]]:=better[ind[i-1]];
            inc(count);
          end
        else
          begin
            if count>0 then bit.update(last,count);
            count:=1; last:=b[i];
            better[ind[i]]:=bit.get(b[i]);
          end;
      for i:=1 to n do
        writeln(f2,better[i]);
    end;

begin
  openF;
  inp;
  sort(1,n);
  solve;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define maxn 300011
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i, a, b) for(int i = int(a); i <= int(b); i++)
#define FORD(i, a, b) for(int i = int(a); i >= int(b); i--)
//#include <conio.h>
//#define g 9.81

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

struct Point{
    int d1, d2, id;
    Point(){};
    Point(int _d1, int _d2, int _id){
        d1 = _d1;
        d2 = _d2;
        id = _id;
    }
    bool operator <(Point P)const{
        if(d1 != P.d1) return d1 < P.d1;
        return d2 < P.d2;
    }
};

Point A[maxn];
int n, x, y, f[100011] = {0}, res[maxn];

void update(int x){
    while(x <= 100001){
        f[x]++;
        x += x & -x;
    }
}

int get(int x){
    int ret = 0;
    while(x > 0){
        ret += f[x];
        x -= x & -x;
    }
    return ret;
}

int main(){
    //OPEN();
    scanf("%d", &n);
    rep(i, n){
        scanf("%d %d", &x, &y);
        x++, y++;
        A[i] = Point(x, y, i);
    }
    sort(A, A + n);
    rep(i, n){
        if(i > 0 && A[i].d1 == A[i - 1].d1 && A[i].d2 == A[i - 1].d2){
            res[A[i].id] = res[A[i - 1].id];
        }
        else res[A[i].id] = get(A[i].d2);
        update(A[i].d2);
    }
    rep(i, n) printf("%d\n",res[i]);
}

Code mẫu của ll931110

{$MODE DELPHI}
Program CRATE;
Const
  input  = '';
  output = '';
  maxn = 300000;
  maxd = 100000;
Type
  rec = record
    x,y,z: integer;
  end;
Var
  a: array[1..maxn] of rec;
  res: array[1..maxn] of integer;
  p: array[1..maxd] of integer;
  n: integer;

Procedure init;
Var
  f: text;
  i: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Readln(f, a[i].x, a[i].y);
      a[i].z:= i;
    End;

  Close(f);
End;

Procedure swap(var s,t: rec);
Var
  tmp: rec;
Begin
  tmp:= s;
  s:= t;
  t:= tmp;
End;

Function low(s,t: rec): boolean;
Begin
  low:= (s.x < t.x) or ((s.x = t.x) and (s.y < t.y));
End;

Procedure quicksort;

  Procedure partition(l,h: integer);
  Var
    i,j: integer;
    pivot: rec;
  Begin
    If l >= h then exit;
    i:= l;
    j:= h;
    pivot:= a[random(h - l + 1) + l];

    Repeat
      While low(a[i],pivot) do inc(i);
      While low(pivot,a[j]) do dec(j);

      If i <= j then
        Begin
          If i < j then swap(a[i],a[j]);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,n);
End;

Procedure update(v: integer);
Begin
  While v <= maxd do
    Begin
      inc(p[v]);
      v:= v + (v and (-v));
    End;
End;

Function calc(v: integer): integer;
Var
  t: integer;
Begin
  t:= 0;
  While v > 0 do
    Begin
      t:= t + p[v];
      v:= v - (v and (-v));
    End;

  calc:= t;
End;

Procedure solve;
Var
  i: integer;
Begin
  Fillchar(p, sizeof(p), 0);
  res[a[1].z]:= 0;
  update(a[1].y);

  For i:= 2 to n do
    Begin
      If (a[i].x = a[i - 1].x) and (a[i].y = a[i - 1].y)
         then res[a[i].z]:= res[a[i - 1].z] else res[a[i].z]:= calc(a[i].y);
      update(a[i].y);
    End;
End;

Procedure printresult;
Var
  f: text;
  i: integer;
Begin
  Assign(f, output);
    Rewrite(f);
    For i:= 1 to n do writeln(f, res[i]);
  Close(f);
End;

Begin
  init;
  quicksort;
  solve;
  printresult;
End.

Code mẫu của khuc_tuan

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Coder {
    int a, b;
    int id;

    bool operator<(Coder c)const {
        if(a==c.a) return b < c.b;
        else return a < c.a;    
    }   
};

int n;
Coder coder[300030];
int res[300010], bit[100010];

int get(int i) {
    int r = 0;
    for(;i>0;i-=i&(-i))r+=bit[i];
    return r;
}

void update(int i){
    for(;i<100010;i+=i&(-i))bit[i]++;
}

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) {
        scanf("%d%d", &coder[i].a, &coder[i].b);
        coder[i].id = i;
    }
    sort(coder,coder+n);
    for(int i=0;i<n;++i) {
        int j = i;
        while(j < n && coder[j].a == coder[i].a) ++j;
        --j;
        for(int k=i;k<=j;++k) {
            res[coder[k].id] += get(coder[k].b+1);
        }
        for(int k=i;k<=j;++k)
            update(coder[k].b+1);
        int st = i;
        for(int k=i;k<=j;++k) {
            while(st <= j && coder[st].b < coder[k].b) ++st;
            res[coder[k].id] += st - i;
        }
        i = j;
    }
    for(int i=0;i<n;++i) printf("%d\n", res[i]);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.