Submission #998035

#	Time	Username	Problem	Language	Result	Execution time	Memory
998035		anHiep	Examination (JOI19_examination)	C++14	100 / 100	518 ms	47684 KiB

examination

#include <bits/stdc++.h>
 
#define int long long
#define ll long long
#define pb push_back
 
using namespace std;
 
struct point{
    int a, b, c, id, val;
};
vector<point> student;
const int maxn = 1e6 + 10;
int ans[maxn];
 
bool cmp(point x, point y){
    if(x.a != y.a) return x.a > y.a;
    if(x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}
 
void inv(point &a){
    a.a = -a.a;
    a.b = -a.b;
    a.c = -a.c;
}
 
int bit[maxn];
 
int getsum(int i){
    ll sum = 0;
    while(i > 0){
        sum+=bit[i];
        i-=(i & (-i));
    }
    return sum;
}
 
void update(int i, int v){
    while(i < maxn){
        bit[i]+=v;
        i+=(i & (-i));
    }
}
 
void dnc(int l, int r){
    if(l + 1 == r) return;
    int mid = (l + r)/2;
    dnc(l , mid); dnc(mid, r);
    vector<pair<int,int>> rec; vector<point> tmp;
    int a = l, b = mid, sum = 0;
 
    while(a < mid && b < r) {
        if(student[a].b > student[b].b){
            update(student[a].c, student[a].val);
            sum+=student[a].val;
            rec.push_back({student[a].c,student[a].val});
            tmp.push_back(student[a++]);
        }
        else{
            ans[student[b].id] += sum - getsum(student[b].c);
            tmp.push_back(student[b++]);
        }
    }
    while(a < mid) tmp.push_back(student[a++]);
    while(b < r) ans[student[b].id] += sum - getsum(student[b].c), tmp.push_back(student[b++]);
    for(int i = l ; i < r ; ++i) student[i] = tmp[i - l];
 
    for(auto x: rec) update(x.first, -x.second);
    vector<pair<int,int>> ().swap(rec);
    vector<point> ().swap(tmp);
}
 
 
signed main(){
    int n, q;
    cin >> n >> q;
    vector<int> compress;
    compress.pb(-1e18); compress.pb(1e18);
    for(int i = 0; i < n; i++){
        point tmp; cin >> tmp.a >> tmp.b;
        tmp.c = tmp.a + tmp.b; tmp.id = 0; tmp.val = 1;
        // inv(tmp);
        compress.pb(tmp.a);compress.pb(tmp.b);compress.pb(tmp.c);
        student.pb(tmp);
    }
 
    int cnt = 1;
    int _q = q;
    while(q--){
        point tmp;
        cin >> tmp.a >> tmp.b >> tmp.c;
        tmp.a--; tmp.b--; tmp.c--;
        tmp.val = 0 ;
        compress.pb(tmp.a); compress.pb(tmp.b); compress.pb(tmp.c);
        tmp.id = cnt;
        // inv(tmp);
        cnt++;
        student.pb(tmp);
    }
    sort(compress.begin(),compress.end());
    for(auto &x : student){
        x.a = lower_bound(compress.begin(),compress.end(),x.a) - compress.begin();
        x.b = lower_bound(compress.begin(),compress.end(),x.b) - compress.begin();
        x.c = lower_bound(compress.begin(),compress.end(),x.c) - compress.begin();
    }
    sort(student.begin(),student.end(), cmp);
 
    dnc(0, n + _q);
 
    for(int i = 1; i <= _q; i++){
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57