Submission #1347300

#TimeUsernameProblemLanguageResultExecution timeMemory
1347300liangjeremyExamination (JOI19_examination)C++20
0 / 100
331 ms10732 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std; 

struct node{
    int tp; int x; int y; int z; int idx; 
}; 
bool cmp1(node a, node b){
    return a.x>b.x; 
}
bool cmp2(node a, node b){
    return a.y>b.y; 
}

vector<node>v; vector<int>ans; vector<int>bits; 
void update(int index, int delta){
    while(index<bits.size()){
        bits[index]+=delta; index+=index&-index; 
    }
}
int query(int index){
    int ans=0; 
    while(index>0){
        ans+=bits[index]; index-=index&-index; 
    }
    return ans; 
}

void cdq(int l, int r){
    if(l==r)return; 
    int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r); vector<int>zcord; 
    for(int i=l; i<=mid; i++){
        if(v[i].tp==0)zcord.push_back(v[i].z); 
    }
    for(int i=mid+1; i<=r; i++){
        if(v[i].tp==1)zcord.push_back(v[i].z); 
    }
    sort(zcord.begin(),zcord.end()); zcord.erase(unique(zcord.begin(),zcord.end()),zcord.end()); bits.clear(); int sz=zcord.size()+10; bits.resize(sz+5); 
    auto get=[&](int val){
        return lower_bound(zcord.begin(),zcord.end(),val)-zcord.begin()+5;  
    }; 
    sort(v.begin()+l,v.begin()+mid+1,cmp2); sort(v.begin()+mid+1,v.begin()+r+1,cmp2); int idx=l; 
    for(int i=mid+1; i<=r; i++){
        while(idx<=mid && v[idx].y>=v[i].y){
            if(v[idx].tp==0)update(get(v[idx].z),1); idx++; 
        }
        if(v[i].tp==1)ans[v[i].idx]+=query(sz)-query(get(v[i].z)-1); 
    }
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int n,q; cin>>n>>q; v.resize(n+q+1); ans.resize(q+1); 
    for(int i=1; i<=n; i++){
        cin>>v[i].x>>v[i].y; v[i].z=v[i].x+v[i].y; 
    }
    for(int i=1; i<=q; i++){
        cin>>v[n+i].x>>v[n+i].y>>v[n+i].z; v[n+i].tp=1; v[n+i].idx=i; 
    }
    sort(v.begin()+1,v.end(),cmp1); cdq(1,n+q); 
    for(int i=1; i<=q; i++){ cout<<ans[i]<<'\n'; }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...