Submission #1128193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128193		KhoaDuy	Examination (JOI19_examination)	C++17	100 / 100	560 ms	34620 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
/*
-READ THE CONSTRAINTS OF THE PROBLEM CAREFULLY.
-ALWAYS WRITE OUT HOW THE CODE WORKS IN YOUR HEAD
(ESPECIALLY THE CASEWORK PARTS) BEFORE CODING ANYTHING.
*/
struct cube{
    int a,b,c,idx;
};
const int MAXN=2*1e5;
int ans[MAXN]={0};
int bit[MAXN+1]={0};
void update(int i,int x){
    for(;i<=MAXN;i+=(i&(-i))){
        bit[i]+=x;
    }
}
int query(int i){
    int curr=0;
    for(;i;i-=(i&(-i))){
        curr+=bit[i];
    }
    return curr;
}
int range(int l,int r){
    if(l>r){
        return 0;
    }
    return (query(r)-query(l-1));
}
bool cmp(cube &x,cube &y){
    if(x.a!=y.a){
        return (x.a<y.a);
    }
    return (x.idx>y.idx);
}
bool cmp2(cube &x,cube &y){
    return (x.b<y.b);
}
void dnc(vector<cube> &v){
    if(v.size()<=1){
        return;
    }
    int mid=v.size()/2;
    vector<cube> vle,vri;
    for(int i=0;i<mid;i++){
        vle.push_back(v[i]);
    }
    for(int i=mid;i<v.size();i++){
        vri.push_back(v[i]);
    }
    dnc(vle);
    dnc(vri);
    sort(vle.begin(),vle.end(),cmp2);
    sort(vri.begin(),vri.end(),cmp2);
    int ptr=vri.size();
    for(int i=vle.size()-1;i>=0;i--){
        while(ptr>0&&vri[ptr-1].b>=vle[i].b){
            ptr--;
            if(vri[ptr].idx==-1){
                update(vri[ptr].c,1);
            }
        }
        if(vle[i].idx!=-1){
            ans[vle[i].idx]+=range(vle[i].c,MAXN);
        }
    }
    for(int i=ptr;i<vri.size();i++){
        if(vri[i].idx==-1){
            update(vri[i].c,-1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    vector<cube> v(n+q);
    map<int,int> mp;
    for(int i=0;i<n;i++){
        cin >> v[i].a >> v[i].b;
        v[i].c=v[i].a+v[i].b;
        v[i].idx=-1;
    }
    for(int i=0;i<q;i++){
        cin >> v[n+i].a >> v[n+i].b >> v[n+i].c;
        v[n+i].idx=i;
    }
    for(int i=0;i<v.size();i++){
        mp[v[i].c]=1;
    }
    int idx=1;
    for(pair<const int,int> &x:mp){
        x.second=idx;
        idx++;
    }
    for(int i=0;i<v.size();i++){
        v[i].c=mp[v[i].c];
    }
    sort(v.begin(),v.end(),cmp);
    dnc(v);
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

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