oj.uz

Submission #402834

# Submission time Handle Problem Language Result Execution time Memory
402834 2021-05-12T12:14:01 Z bigDuck Examination (JOI19_examination) C++14
2 / 100
 3000 ms 661224 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, 0, 1e9, 0, 1e9, pr[ind].sc.ft, pr[ind].sc.sc);
        ind--;
    }
    res[qr[i].sc.ft ]=query1(t1, 0, 1e9, 0, 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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 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 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 144 ms 85176 KB Output is correct
8 Correct 138 ms 85176 KB Output is correct
9 Correct 140 ms 85192 KB Output is correct
10 Correct 95 ms 59908 KB Output is correct
11 Correct 102 ms 58196 KB Output is correct
12 Correct 24 ms 576 KB Output is correct
13 Correct 140 ms 85256 KB Output is correct
14 Correct 139 ms 85288 KB Output is correct
15 Correct 139 ms 85352 KB Output is correct
16 Correct 102 ms 57292 KB Output is correct
17 Correct 93 ms 59076 KB Output is correct
18 Correct 21 ms 528 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3125 ms 661224 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 3125 ms 661224 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 332 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 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 144 ms 85176 KB Output is correct
8 Correct 138 ms 85176 KB Output is correct
9 Correct 140 ms 85192 KB Output is correct
10 Correct 95 ms 59908 KB Output is correct
11 Correct 102 ms 58196 KB Output is correct
12 Correct 24 ms 576 KB Output is correct
13 Correct 140 ms 85256 KB Output is correct
14 Correct 139 ms 85288 KB Output is correct
15 Correct 139 ms 85352 KB Output is correct
16 Correct 102 ms 57292 KB Output is correct
17 Correct 93 ms 59076 KB Output is correct
18 Correct 21 ms 528 KB Output is correct
19 Execution timed out 3125 ms 661224 KB Time limit exceeded
20 Halted 0 ms 0 KB -