Submission #959344

#	Time	Username	Problem	Language	Result	Execution time	Memory
959344		irmuun	Examination (JOI19_examination)	C++17	41 / 100	225 ms	40868 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);
    ll n,q;
    cin>>n>>q;
    ll s[n],t[n];
    const ll N=2e5;
    vector<ll>upd[N+5],upd2[N+5];
    for(ll i=0;i<n;i++){
        cin>>s[i]>>t[i];
        upd[s[i]].pb(t[i]);
        upd2[s[i]+t[i]].pb(i);
    }
    ll x[q],y[q],z[q];
    vector<ll>ans(q,0);
    vector<pair<ll,ll>>ask[N+5];
    vector<ll>que[N+5];
    for(ll i=0;i<q;i++){
        cin>>x[i]>>y[i]>>z[i];
        if(z[i]<=x[i]+y[i]){
            ask[x[i]].pb({y[i],i});
        }
        else{
            que[z[i]].pb(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);
    }
    for(ll i=N;i>=0;i--){
        for(auto j:upd2[i]){
            sg.update(1,0,N,s[j],1);
        }
        for(auto j:que[i]){
            ans[j]=sg.query(1,0,N,x[j],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:upd2[i]){
            sg.update(1,0,N,t[j],1);
        }
        for(auto j:que[i]){
            ans[j]-=sg.query(1,0,N,0,y[j]-1);
        }
    }
    for(ll i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}

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