Submission #1201449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201449		KhoaDuy	Examination (JOI19_examination)	C++17	100 / 100	408 ms	21096 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=2*1e5;
struct fenwick{
    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));
    }
};
fenwick bit;
struct cube{
    int a,b,c,idx;
};
struct cdq{
    vector<long long> ans;
    static bool cmp(cube &x,cube &y){
        if(x.a!=y.a){
            return (x.a<y.a);
        }
        return (x.idx>y.idx);
    }
    static bool cmp2(cube &x,cube &y){
        return (x.b<y.b);
    }
    void add(cube &x){
        bit.update(x.c,1);
    }
    void del(cube &x){
        bit.update(x.c,-1);
    }
    void query(cube &x){
        ans[x.idx]+=bit.range(x.c,MAXN);
    }
    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){
                    add(vri[ptr]);
                }
            }
            if(vle[i].idx!=-1){
                query(vle[i]);
            }
        }
        for(int i=ptr;i<vri.size();i++){
            if(vri[i].idx==-1){
                del(vri[i]);
            }
        }
    }
    vector<long long> solve(vector<cube> &v){
        int Max=0;
        for(int i=0;i<v.size();i++){
            Max=max(Max,v[i].idx);
        }
        ans.resize(Max+1);
        sort(v.begin(),v.end(),cmp);
        dnc(v);
        return ans;
    }
};
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];
    }
    cdq bruh;
    vector<long long> ans=bruh.solve(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