Submission #959381

#	Time	Username	Problem	Language	Result	Execution time	Memory
959381		irmuun	Examination (JOI19_examination)	C++17	100 / 100	920 ms	71536 KiB

examination

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,0,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0ll;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]+=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
    void set(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        set(node*2,l,mid,k,val);
        set(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    const ll N=2e5;
    ll n,q;
    cin>>n>>q;
    ll s[n],t[n];
    set<ll>S,T,Z;
    for(ll i=0;i<n;i++){
        cin>>s[i]>>t[i];
        S.insert(s[i]);
        T.insert(t[i]);
        Z.insert(s[i]+t[i]);
    }
    ll x[q],y[q],z[q];
    vector<ll>ans(q,0);
    for(ll i=0;i<q;i++){
        cin>>x[i]>>y[i]>>z[i];
        S.insert(x[i]);
        T.insert(y[i]);
        Z.insert(z[i]);
    }
    ll Sc=S.size(),Tc=T.size(),Zc=Z.size();
    ll Sa[Sc],Ta[Tc],Za[Zc],cur=0;
    for(auto x:S){
        Sa[cur++]=x;
    }
    cur=0;
    for(auto x:T){
        Ta[cur++]=x;
    }
    cur=0;
    for(auto x:Z){
        Za[cur++]=x;
    }
    //case1 x[i]+y[i]>=z[i]
    vector<ll>upd[N+5];
    vector<pair<ll,ll>>ask[N+5];
    for(ll i=0;i<n;i++){
        ll p=lower_bound(Sa,Sa+Sc,s[i])-Sa;
        ll q=lower_bound(Ta,Ta+Tc,t[i])-Ta;
        upd[p].pb(q);
    }
    for(ll i=0;i<q;i++){
        if(x[i]+y[i]>=z[i]){
            ll p=lower_bound(Sa,Sa+Sc,x[i])-Sa;
            ll q=lower_bound(Ta,Ta+Tc,y[i])-Ta;
            ask[p].pb({q,i});
        }
    }
    segtree sg(N);
    for(ll i=N;i>=0;i--){
        for(auto y:upd[i]){
            sg.update(1,0,N,y,1);
        }
        for(auto [y,j]:ask[i]){
            ans[j]=sg.query(1,0,N,y,N);
        }
    }
    for(ll i=0;i<=N;i++){
        sg.set(1,0,N,i,0);
        upd[i].clear();
    }
    for(ll i=0;i<n;i++){
        ll p=lower_bound(Za,Za+Zc,s[i]+t[i])-Za;
        upd[p].pb(i);
    }
    vector<ll>que[N+5];
    for(ll i=0;i<q;i++){
        if(x[i]+y[i]<z[i]){
            ll p=lower_bound(Za,Za+Zc,z[i])-Za;
            que[p].pb(i);
        }
    }
    for(ll i=N;i>=0;i--){
        for(auto j:upd[i]){
            ll p=lower_bound(Sa,Sa+Sc,s[j])-Sa;
            sg.update(1,0,N,p,1);
        }
        for(auto j:que[i]){
            ll p=lower_bound(Sa,Sa+Sc,x[j])-Sa;
            ans[j]=sg.query(1,0,N,p,N);
        }
    }
    for(ll i=0;i<=N;i++){
        sg.set(1,0,N,i,0);
    }
    for(ll i=N;i>=0;i--){
        for(auto j:upd[i]){
            ll p=lower_bound(Ta,Ta+Tc,t[j])-Ta;
            sg.update(1,0,N,p,1);
        }
        for(auto j:que[i]){
            ll p=lower_bound(Ta,Ta+Tc,y[j])-Ta;
            ans[j]-=sg.query(1,0,N,0,p-1);
        }
    }
    for(ll i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}

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