Submission #1116987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116987		Newtonabc	Examination (JOI19_examination)	C++14	0 / 100	138 ms	78408 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2e6+(1<<18);
int b[N],sum[N],cnt=1,froot[N],sroot[N];
pair<int,int> arr[N];
struct{
    int l,r;
    long long val;
}s[M];
int clone(int x){s[++cnt]=s[x]; return cnt;}
struct persist{
    void build(int l,int r,int idx){
        cnt=max(cnt,idx);
        if(l==r){
            s[idx]={0,0,0};
            return;
        }
        int m=(l+r)/2;
        build(l,m,idx*2);
        build(m+1,r,idx*2+1);
        s[idx].l=idx*2,s[idx].r=idx*2+1;
        s[idx].val=s[idx*2].val+s[idx*2+1].val;
    }
    int update(int l,int r,int idx,int a,int b){
        int now=clone(idx);
        if(l==r){
            s[now].val+=b;
            return now;
        }
        int m=(l+r)/2;
        if(a<=m) s[now].l=update(l,m,s[idx].l,a,b);
        else s[now].r=update(m+1,r,s[idx].r,a,b);
        s[now].val=s[s[now].l].val+s[s[now].r].val;
        return now;
    }
    int query(int l,int r,int idx,int a,int b){
        if(a>r || b<l) return 0;
        if(a<=l && b>=r) return s[idx].val;
        int m=(l+r)/2;
        return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
    }
}ftree,stree;

int main(){
    int n,q;
    cin>>n >>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i].first >>arr[i].second;
        b[i]=arr[i].second;
        sum[i]=arr[i].first+arr[i].second;
    }
    sort(arr+1,arr+n+1);
    sort(b+1,b+n+1);
    sort(sum+1,sum+n+1);
    ftree.build(1,n,1);
    stree.build(1,n,1);
    froot[0]=sroot[0]=1;
    for(int i=1;i<=n;i++){
        int tb=lower_bound(b+1,b+n+1,arr[i].second)-b;
        int ts=lower_bound(sum+1,sum+n+1,arr[i].first+arr[i].second)-sum;
        froot[i]=ftree.update(1,n,froot[i-1],tb,1);
        sroot[i]=stree.update(1,n,sroot[i-1],ts,1);
    }
    while(q--){
        int x,y,z,ans=0;
        cin>>x >>y >>z;
        int ta=lower_bound(arr+1,arr+n+1,make_pair(x,0))-arr;
        int md=lower_bound(arr+ta,arr+n+1,make_pair(z-y,0))-arr;
        int fb=lower_bound(b+1,b+n+1,y)-b;
        int fs=lower_bound(sum+1,sum+n+1,z)-sum;
        ans+=ftree.query(1,n,froot[n],fb,n)-ftree.query(1,n,froot[md-1],fb,n);
        ans+=stree.query(1,n,sroot[md-1],fs,n)-ftree.query(1,n,froot[ta-1],fs,n);
        cout<<ans <<"\n";
    }
}

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