auto_racer_1.cpp

/*
    by cpcs
*/
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

vector<int> tree; //segment tree saves how many numbers in the segment
map<ll,int> alltime;  // oldtime->new time

struct record {
ll start,end;
int id,score;
};

vector<record> data;  //all the records

inline bool cmpbyend(const record &a,const record &b) {
    return a.end < b.end;
}

inline bool cmpbyscore(const record &a,const record &b) {
    return (a.score < b.score) || ((a.score == b.score) && (a.id < b.id));
}

void insert(int ind,int left,int right,int x) { //add one number x
    ++tree[ind];
    if (left == right) {
        return;
    }
    int mid = (left + right) >> 1;
    if (x <= mid) {
        insert(ind << 1, left ,mid, x);
    }
    else {
        insert((ind << 1) | 1, mid + 1, right, x);
    }
}

int getseg(int ind,int left,int right,int x1,int x2) { // get number of [x1..x2]
    if ((left == x1) && (right == x2)) {
        return tree[ind];
    }
    int mid = (left + right) >> 1;
    if (x2 <= mid) {
        return getseg(ind << 1, left, mid, x1, x2);
    }
    if (x1 > mid) {
        return getseg((ind << 1) | 1, mid + 1, right, x1, x2);
    }
    return getseg(ind << 1, left, mid, x1 ,mid) + getseg((ind << 1) | 1, mid + 1, right, mid + 1, x2);
}

int main() {
    int n,i,m;
    map<ll,int>::iterator t;

    scanf("%d",&n);
    data.resize(n);
    for (i = 0; i < n; ++i) {
        scanf("%d%lld%lld",&data[i].id,&data[i].start,&data[i].end);
        ++alltime[data[i].start];
    }

    i = 0;
    for (t = alltime.begin(); t != alltime.end(); ++t) {  //change time to smaller segment
        t->second = i++;
    }

    m = i;  // so all the number lies in [0..m - 1] because we want add 1 later so we use m here
    tree.resize((m + 1) << 2,0);
    sort(data.begin(),data.end(),cmpbyend);  //sort by end time
    for (i = 0; i < n; ++ i) {
        data[i].score = getseg(1, 0, m, alltime[data[i].start] + 1, m);  //find how many numbers in [start + 1.. m]
        insert(1, 0 , m, alltime[data[i].start]);
    }

    sort(data.begin(),data.end(),cmpbyscore);  // sort by demand
    for (i = 0; i < n; ++i) {
        printf("%d %d\n",data[i].id,data[i].score);
    }
    return 0;
}