oj.uz

Submission #402832

# Submission time Handle Problem Language Result Execution time Memory
402832 2021-05-12T12:11:17 Z bigDuck Examination (JOI19_examination) C++14
0 / 100
 3000 ms 661712 KB 
#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];


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]} };
}
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;
}
sort(qr+1, qr+1+q);

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

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


return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 141 ms 85084 KB Output is correct
8 Correct 139 ms 85060 KB Output is correct
9 Correct 138 ms 85180 KB Output is correct
10 Incorrect 94 ms 59804 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 661712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 661712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 141 ms 85084 KB Output is correct
8 Correct 139 ms 85060 KB Output is correct
9 Correct 138 ms 85180 KB Output is correct
10 Incorrect 94 ms 59804 KB Output isn't correct
11 Halted 0 ms 0 KB -