ĐỀ BÀI :

CODER RATING – CRATE – SPOJ

Cho danh sách N lập trình viên (1 ≤ N ≤ 300000), đánh số lần lượt từ 1 đến N. Mỗi người đều tham gia cả hai giải thi đấu: Giải THPT và giải Mở rộng. Với mỗi lập trình viên, bạn sẽ được cung cấp điểm số của giải Mở rộng Ai và điểm số của giải THPT Hi (Các điểm số đều là số nguyên không âm và không vượt quá 100000). Lập trình viên i được coi là giỏi hơn lập trình viên j khi và chỉ khi cả 2 điểm số của lập trình viên i đều lớn hơn hoặc bằng điểm số tương ứng của lập trình viên j, trong đó có ít nhất 1 điểm số phải lớn hơn. Hãy tính xem với mỗi lập trình viên i thì có bao nhiêu lập trình viên mà i giỏi hơn.

Input

Dòng đầu tiên chứa số nguyên N.

N dòng tiếp theo, dòng thứ i+1 chứa 2 số nguyên Ai và Hi.

Output

Dòng i chứa số lượng lập trình viên mà lập trình viên i giỏi hơn.

Example

Input: 8 1798 1832 862 700 1075 1089 1568 1557 2575 1984 1033 950 1656 1649 1014 1473 Output: 6 0 2 4 7 1 5 1

Bài gốc: https://www.spoj.pl/problems/RATING/

THUẬT TOÁN :

Bài này có thể dùng IT hoặc BIT (hình như là vậy).

Mình sẽ dùng IT :

< Các bạn có thể tham khảo thêm ở cuốn Một số vấn đề đáng chú ý trong môn tin học mình đã share với các bạn. nên xem trước thuật toán để hiểu dễ hơn >

Cách làm :

Ở bài này, giới hạn của bài toán khá lớn (300000) nên nếu dùng N log N thì cũng còn nguy hiểm. Chú ý giới hạn của số điểm là 0..100000 nên ta sẽ xử lí trên số điểm.

+ Tạo một danh sách các thông tin của từng người: struct(C++) hay record(pascal) ds gồm d1,d2 là điểm lần 1 và 2, vt là vị trí ban đầu của nó. Mảng A sẽ lưu danh sách này

+ Tạo một mảng res sẽ chứa mảng cần xuất ra khi đã thực hiện xong chương trình. Cách tạo res là for i = 1 -> n rồi lưu res[a[i].vt] = giá trị tìm được của thằng a[i].vt (vị trí ban đầu của nó). Sau đó xuất ra theo thứ tự trong res thôi.

+ Tạo một cây IT là mảng t[k] lưu thông tin của nút k quản lí đoạn l..r (xét trên số điểm) và một mảng f lưu nghiệm của bài toán, tức là f[i] là số lượng những thằng tồi hơn thằng i sau khi đã sort lại (như tài liệu đã nói) (cách sort của tài liệu xem thêm ở code) ( C++ code đơn giản hơn pascal )

+ Tạo thêm biến m lưu số điểm d2 lớn nhất vì theo như tài liệu d1 ta đã sort lại rồi thì không cần quan tâm điểm lớn hay nhỏ.

+ Sau khi nhập dữ liệu thì sort lại dãy

+ Tạo biến q là vị trí đang duyệt trên dãy a ( từ 1 -> n , lần lượt xét các đoạn có cùng d1). Khi q > n thì xuất nghiệm ra, halt luôn. trước hết q = 0

+ Tạo biến L và R lưu đoạn xét nói trên. Khi đó ban đầu L = q và R = q. lần lượt tăng R lên đến khi d1 thay đổi. Xong thì xét đoạn L..R mới tìm được

+Khởi tạo f[L] = 0. Tạo f.

+ Sau đó lấy giá trị cho f trên cây t ( nhớ là xét trên số điểm từ 0..m, -đoạn ban đầu findans) : điểm đang xét là x. ta sẽ tìm những đoạn mà r <= x để lấy ans còn những đoạn nào mà x < l ( điểm thấp hơn ) thì ta bỏ qua. trường hợp còn lại thì chia ra 2 đoạn mà làm như các bài it cơ bản

+ Lấy giá trị xong thì cập nhật lại cây t. : bỏ qua những đoạn x không thuộc. tăng số lượng nút này lên. nếu l = r thì thôi. chia hai đoạn để it.

+ q = R.

+ Duyệt đến chết thì thôi

CODE :

C++ :

include <iostream>

include <fstream>

include <cstdio>

include <cstdlib>

include <algorithm>

include <cmath>

using namespace std;

struct ds {     int d1,d2,vt; };

const int       maxn = 300010, maxt = maxn*4 + 1; int             n,m,q,L,R; ds              a[maxn]; int             t[maxt],f[maxn],res[maxn];

void findans(int k, int l, int r, int x, int &ans) {     if (x < l) return;     if (r <= x) {         ans += t[k];         return;     }     int m = (l+r)/2;     findans(k*2,l,m,x,ans);     findans(k*2+1,m+1,r,x,ans); }

void update(int k, int l, int r, int x) {     if (x < l or r < x) return;     t[k]++;     if (l == r) return;     int m  = (l+r)/2;     update(k*2,l,m,x);     update(k*2+1,m+1,r,x); }

 bool compare(const ds u, const ds v) {     if (u.d1 < v.d1) return true;     if (u.d1 == v.d1 and u.d2 < v.d2) return true;     return false; }

int main(){     scanf("%d",&n);     for (int i=1;i<=n;i++) {         scanf("%d%d",&a[i].d1,&a[i].d2);         a[i].vt = i;         m = max(m,a[i].d2);     }     //-----//     sort(a+1,a+n+1,compare);     q = 0;     while (1 == 1) {         q++;         if (q > n) {             for (int i=1;i<=n;i++) res[a[i].vt] = f[i];             for (int i=1;i<=n;i++) printf("%d\n",res[i]);             return 0;         }         L = q;         R = q;         while (R < n and a[R].d1 == a[R+1].d1) R++;         f[L] = 0;         for (int i=L+1;i<=R;i++)             if (a[i].d2 <= a[i-1].d2) f[i] = f[i-1];             else f[i] = i - L;         for (int i=L;i<=R;i++) {             int ans = 0;             findans(1,0,m,a[i].d2,ans);             f[i] += ans;         }         for (int i=L;i<=R;i++) update(1,0,m,a[i].d2);         q = R;     }

    return 0; }

Pascal :

CONST   maxn = 300010;         maxt = maxn*4+1;

TYPE    ds   = record                 d1,d2,vt : longint;         end;

VAR     n,m,i,j,l,r,q,ans   : longint;         a                   : array[0..maxn] of ds;         res,f               : array[0..maxn] of longint;         t                   : array[0..maxt] of longint;

//-------//

function compare(x,y : ds) : boolean;  begin         if (x.d1 < y.d1) then exit(true);         if (x.d1 = y.d1) and (x.d2 < y.d2) then exit(true);         exit(false);  end;

procedure sort(l,r : longint);  var    i,j   : longint;         x,tmp : ds;  begin         i := l;         j := r;         x := a[(l+r) div 2];         repeat                 while compare(a[i],x) do inc(i);                 while compare(x,a[j]) do dec(j);                 if i <= j then begin                         tmp  := a[i];                         a[i] := a[j];                         a[j] := tmp;                         inc(i);                         dec(j);                 end;         until                 i > j;         if l < j then sort(l,j);         if i < r then sort(i,r);  end;

//--------//

procedure findans(k,l,r,x : longint; var ans : longint);  var    i,j,m : longint;  begin         if x < l then exit;         if x >= r then begin                 ans := ans + t[k];                 exit;         end;         m := (l+r) div 2;         findans(k*2,l,m,x,ans);         findans(k*2+1,m+1,r,x,ans);  end;

procedure update(k,l,r,x : longint);  var    m : longint;  begin         if (x < l) or (r < x) then exit;         t[k] := t[k] + 1;         if (l = r) then exit;         m := (l+r) div 2;         update(k*2,l,m,x);         update(k*2+1,m+1,r,x);  end;

//------//

BEGIN

        readln(n);         for i := 1 to n do begin                 readln(a[i].d1,a[i].d2);                 a[i].vt := i;                 if (m < a[i].d2) then m := a[i].d2;         end;

        sort(1,n);

        q := 0;         while (1 = 1) do begin                 q := q + 1;                 if (q > n) then begin                         for i := 1 to n do res[a[i].vt] := f[i];                         for i := 1 to n do writeln(res[i]);                         halt;                 end;                 l := q;                 r := q;                 while (r < n) and (a[r+1].d1 = a[l].d1) do inc(r);                 f[l] := 0;                 for i := l+1 to r do                         if a[i].d2 <= a[i-1].d2 then                                 f[i] := f[i-1]                         else                                 f[i] := i-l;                 for i := l to r do begin                         ans := 0;                         findans(1,0,m,a[i].d2,ans);                         f[i] := f[i] + ans;                 end;                 for i := l to r do update(1,0,m,a[i].d2);                 q := r;         end;  end.