Submission #1053628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053628		hotboy2703	Examination (JOI19_examination)	C++17	100 / 100	428 ms	64208 KiB

examination

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e5+100;
const ll INF = 1e18;
ll dp[MAXN];
ll n,q;
pll a[MAXN];
vector <ll> tree1[MAXN*4],tree2[MAXN*4];
vector <ll> val;
void update(ll id,ll l,ll r,ll pos){
    if (val[l] > a[pos].fi || val[r] < a[pos].fi)return;
    tree1[id].push_back(a[pos].se);
    tree2[id].push_back(a[pos].fi + a[pos].se);   
    if (l == r){
        return;
    }
    ll mid = (l + r) >> 1;
    update(id<<1,l,mid,pos);
    update(id<<1|1,mid+1,r,pos);
}
void build(ll id,ll l,ll r){
    sort(tree1[id].begin(),tree1[id].end());
    sort(tree2[id].begin(),tree2[id].end());
    // cout<<id<<' '<<l<<' '<<r<<'\n';
    // cout<<"tree1 : ";for (auto x:tree1[id])cout<<x<<' ';cout<<'\n';
    // cout<<"tree2 : ";for (auto x:tree2[id])cout<<x<<' ';cout<<'\n';
    if (l != r){
        ll mid = (l + r) >> 1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
}
vector <ll> all;
ll get1(ll id,ll l,ll r,ll l1, ll B){
    if (val[r] < l1)return 0;
    if (val[l] >= l1){
        return tree1[id].end() - lower_bound(tree1[id].begin(),tree1[id].end(),B);
    }
    ll mid = (l + r) >> 1;
    return get1(id<<1,l,mid,l1,B) + get1(id<<1|1,mid+1,r,l1,B);
}
ll get2(ll id,ll l,ll r,ll l1,ll r1,ll C){
    if (val[l] > r1 || l1 > val[r] || l1 > r1)return 0;
    if (l1 <= val[l] && val[r] <= r1){
        return tree2[id].end() - lower_bound(tree2[id].begin(),tree2[id].end(),C);;
    }
    ll mid = (l + r) >> 1;
    return get2(id<<1,l,mid,l1,r1,C) + get2(id<<1|1,mid+1,r,l1,r1,C);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>q;
    for (ll i = 1;i <= n;i ++){
        
        cin>>a[i].fi>>a[i].se;
        val.push_back(a[i].fi);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    val.insert(val.begin(),0);
    // cout<<"WOW "<<sz(val)<<endl;
    for (ll i = 1;i <= n;i ++){
        update(1,1,sz(val)-1,i);
    }
    build(1,1,sz(val)-1);
    while (q--){
        ll A,B,C;
        cin>>A>>B>>C;
        ll tmp = max(A,C-B);
        cout<<get1(1,1,sz(val)-1,tmp,B)+get2(1,1,sz(val)-1,A,tmp-1,C)<<'\n';
    }
}

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