Submission #1367540

#TimeUsernameProblemLanguageResultExecution timeMemory
1367540NewtonabcExamination (JOI19_examination)C++20
0 / 100
244 ms13612 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<tuple<int,int,int,int,int>> ev;
int si[N],ti[N],gi[N],xi[N],yi[N],zi[N],ret[N];
//point: (s[i],t[i],g[i],0,0)
//query: (x[i],y[i],z[i],1,id)
//for each query (x,y,z) find number of point i where s[i]>=x, t[i]>=y, g[i]>=z
struct QWQ{
    vector<int> fw;
    int sz;
    void init(int n){fw.clear(); fw.resize(n+5,0); sz=n+5;}
    void upd(int i,int val){for(;i<sz;i+=i&-i) fw[i]+=val;}
    int qry(int i){int s=0; for(;i;i-=i&-i) s+=fw[i]; return s;}
}UWU;
void cdq(int l,int r){
    if(l==r) return;
    //find relation between part (l,m) and part (m+1,r)
    int m=(l+r)/2;
    vector<tuple<int,int,int,int,int>> pt;
    for(int i=l;i<=m;i++){
        auto [a,b,c,ti,id]=ev[i];
        if(ti==1) pt.push_back(ev[i]);
    }
    for(int i=m+1;i<=r;i++){
        auto [a,b,c,ti,id]=ev[i];
        if(ti==0) pt.push_back(ev[i]);
    }
    int tsz=pt.size();
    UWU.init(tsz+10);
    vector<int> cn;
    cn.push_back(INT_MIN);
    for(auto [a,b,c,ti,id]:pt){
        cn.push_back(c);
    }
    sort(cn.begin(),cn.end());
    cn.erase(unique(cn.begin(),cn.end()),cn.end());
    sort(pt.begin(),pt.end(),[&](tuple<int,int,int,int,int> &a,tuple<int,int,int,int,int> &b){
        if(get<1>(a)!=get<1>(b)){
            return (get<1>(a))>(get<1>(b));
        }
        //y[i]==y[j] then compare type 0 (point) insert before 1 (query)
        return (get<3>(a))<(get<3>(b));
    });
    for(auto [a,b,c,ti,id]:pt){
        int tc=lower_bound(cn.begin(),cn.end(),c)-cn.begin();
        if(ti==0) UWU.upd(tc,1);
        else ret[id]+=UWU.qry(tsz)-UWU.qry(tc-1);
    }
    cdq(l,m);
    cdq(m+1,r);
}
int main(){
    int n,q; cin>>n >>q;
    for(int i=1;i<=n;i++){
        cin>>si[i] >>ti[i]; gi[i]=si[i]+ti[i];
        ev.push_back({si[i],ti[i],gi[i],0,0});
    }
    for(int i=0;i<q;i++){
        cin>>xi[i] >>yi[i] >>zi[i]; 
        ev.push_back({xi[i],yi[i],zi[i],1,i});
    }
    int tsz=ev.size();
    sort(ev.begin(),ev.end());
    cdq(0,tsz-1);
    for(int i=0;i<q;i++) cout<<ret[i] <<"\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...