Submission #402839

#	Time	Username	Problem	Language	Result	Execution time	Memory
402839		bigDuck	Examination (JOI19_examination)	C++14	100 / 100	2947 ms	691036 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll

int n, m, k, a[300010], q, l, r;



struct n2{
    n2 *l, *r;
    int sum;
    n2(){
        this->l=this->r=NULL;
        this->sum=0;
    }
};


struct n1{
    n1 *l, *r;
    n2 *t2;
    n1(){
        this->l=this->r=NULL;
        this->t2=NULL;
    }
} *t1;



void update2( n2*&t, int l2, int r2, int y){


    if(!t){
        t=new n2();
    }

    if(l2==r2){
        t->sum++;
        return;
    }

    int mid=(l2+r2)>>1ll;
    if(y<=mid){
        update2(t->l, l2, mid, y);

    }
    else{
        update2(t->r, mid+1, r2, y);
    }
    t->sum++;
}




void update1(n1 *&t, int l1, int r1, int l2, int r2, int x, int y){
    if(!t){
        t=new n1();
    }

    update2(t->t2, l2, r2, y);

    if(l1==r1){
        return;
    }
    int mid=(l1+r1)>>1ll;
    if(x<=mid){
        update1(t->l, l1, mid, l2, r2, x, y);
    }
    else{
        update1(t->r, mid+1, r1, l2, r2, x, y);
    }
    return;
}



int query2(n2 *t, int l2, int r2, int y1, int y2){

    if(!t){
        return 0;
    }

    if(y1>y2){
        return 0;
    }
    if( (y1==l2) && (y2==r2) ){
        return t->sum;
    }
    int mid=(l2+r2)>>1ll;
    return query2(t->l, l2, mid, y1, min(mid, y2))+query2(t->r, mid+1, r2, max(mid+1, y1), y2 );
}




int query1(n1 *t, int l1, int r1, int l2, int r2, int x1, int x2,  int y1, int y2){

    if(!t){
        return 0;
    }
    if(x1>x2){
        return 0;
    }

    if( (l1==x1) && (r1==x2) ){
        return query2(t->t2, l2, r2, y1, y2);
    }
    int mid=(l1+r1)>>1ll;
    return query1(t->l, l1, mid, l2, r2, x1, min(x2, mid), y1, y2)+query1(t->r, mid+1, r1, l2, r2, max(mid+1, x1), x2, y1, y2);
}





int s[100010], t[100010];
pair<int, pii> pr[100010];


pair<int, pair<int, pii>> qr[100010];
int res[100010];





map<int, int> ord1, ord2, ord3;
vector<int> v1, v2, v3;


int32_t main(){
INIT


cin>>n>>q;
for(int i=1; i<=n; i++){
    cin>>s[i]>>t[i];
    pr[i]={s[i]+t[i], {s[i], t[i]} };
    v3.pb(s[i]+t[i]);
    v1.pb(s[i]);
    v2.pb(t[i]);
}
sort(pr+1, pr+1+n);




for(int i=1; i<=q; i++){
    cin>>qr[i].sc.sc.ft>>qr[i].sc.sc.sc>>qr[i].ft;
    qr[i].sc.ft=i;
    v1.pb(qr[i].sc.sc.ft); v2.pb(qr[i].sc.sc.sc);
    v3.pb(qr[i].ft);
}
sort(qr+1, qr+1+q);



sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
sort(v3.begin(), v3.end());

int ord=1;
for(auto x:v1){
    ord1[x]=ord; ord++;
}
ord=1;
for(auto x:v2){
    ord2[x]=ord; ord++;
}
ord=1;
for(auto x:v3){
    ord3[x]=ord; ord++;
}









int ind=n;
for(int i=q; i>=1; i--){
    while( (ind>=1) && (pr[ind].ft>=qr[i].ft) ){
        update1(t1, 1, 2*n, 1, 2*n, ord1[pr[ind].sc.ft], ord2[pr[ind].sc.sc]);
        ind--;
    }
    res[qr[i].sc.ft ]=query1(t1, 1, n*2, 1, n*2, ord1[qr[i].sc.sc.ft], n*2, ord2[qr[i].sc.sc.sc], n*2);
}

for(int i=1; i<=q; i++){
    cout<<res[i]<<"\n";
}


return 0;
}

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