oj.uz

Submission #402839

# Submission time Handle Problem Language Result Execution time Memory
402839 2021-05-12T12:20:17 Z bigDuck Examination (JOI19_examination) C++14
100 / 100
 2947 ms 691036 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];





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.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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 34 ms 12320 KB Output is correct
8 Correct 36 ms 12416 KB Output is correct
9 Correct 34 ms 12360 KB Output is correct
10 Correct 22 ms 8012 KB Output is correct
11 Correct 22 ms 7864 KB Output is correct
12 Correct 9 ms 972 KB Output is correct
13 Correct 34 ms 12328 KB Output is correct
14 Correct 41 ms 12204 KB Output is correct
15 Correct 34 ms 12328 KB Output is correct
16 Correct 15 ms 4300 KB Output is correct
17 Correct 16 ms 4884 KB Output is correct
18 Correct 6 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2588 ms 658904 KB Output is correct
2 Correct 2647 ms 661540 KB Output is correct
3 Correct 2641 ms 661296 KB Output is correct
4 Correct 1257 ms 326912 KB Output is correct
5 Correct 1090 ms 318500 KB Output is correct
6 Correct 388 ms 9128 KB Output is correct
7 Correct 2335 ms 627852 KB Output is correct
8 Correct 2326 ms 628808 KB Output is correct
9 Correct 2062 ms 594404 KB Output is correct
10 Correct 660 ms 138900 KB Output is correct
11 Correct 924 ms 152732 KB Output is correct
12 Correct 330 ms 7828 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2588 ms 658904 KB Output is correct
2 Correct 2647 ms 661540 KB Output is correct
3 Correct 2641 ms 661296 KB Output is correct
4 Correct 1257 ms 326912 KB Output is correct
5 Correct 1090 ms 318500 KB Output is correct
6 Correct 388 ms 9128 KB Output is correct
7 Correct 2335 ms 627852 KB Output is correct
8 Correct 2326 ms 628808 KB Output is correct
9 Correct 2062 ms 594404 KB Output is correct
10 Correct 660 ms 138900 KB Output is correct
11 Correct 924 ms 152732 KB Output is correct
12 Correct 330 ms 7828 KB Output is correct
13 Correct 2540 ms 664360 KB Output is correct
14 Correct 2683 ms 663716 KB Output is correct
15 Correct 2778 ms 661520 KB Output is correct
16 Correct 1130 ms 324928 KB Output is correct
17 Correct 1117 ms 326060 KB Output is correct
18 Correct 427 ms 9224 KB Output is correct
19 Correct 2458 ms 664428 KB Output is correct
20 Correct 2623 ms 664204 KB Output is correct
21 Correct 2249 ms 642532 KB Output is correct
22 Correct 690 ms 145936 KB Output is correct
23 Correct 821 ms 152484 KB Output is correct
24 Correct 316 ms 7844 KB Output is correct

Subtask #4
57.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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 34 ms 12320 KB Output is correct
8 Correct 36 ms 12416 KB Output is correct
9 Correct 34 ms 12360 KB Output is correct
10 Correct 22 ms 8012 KB Output is correct
11 Correct 22 ms 7864 KB Output is correct
12 Correct 9 ms 972 KB Output is correct
13 Correct 34 ms 12328 KB Output is correct
14 Correct 41 ms 12204 KB Output is correct
15 Correct 34 ms 12328 KB Output is correct
16 Correct 15 ms 4300 KB Output is correct
17 Correct 16 ms 4884 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 2588 ms 658904 KB Output is correct
20 Correct 2647 ms 661540 KB Output is correct
21 Correct 2641 ms 661296 KB Output is correct
22 Correct 1257 ms 326912 KB Output is correct
23 Correct 1090 ms 318500 KB Output is correct
24 Correct 388 ms 9128 KB Output is correct
25 Correct 2335 ms 627852 KB Output is correct
26 Correct 2326 ms 628808 KB Output is correct
27 Correct 2062 ms 594404 KB Output is correct
28 Correct 660 ms 138900 KB Output is correct
29 Correct 924 ms 152732 KB Output is correct
30 Correct 330 ms 7828 KB Output is correct
31 Correct 2540 ms 664360 KB Output is correct
32 Correct 2683 ms 663716 KB Output is correct
33 Correct 2778 ms 661520 KB Output is correct
34 Correct 1130 ms 324928 KB Output is correct
35 Correct 1117 ms 326060 KB Output is correct
36 Correct 427 ms 9224 KB Output is correct
37 Correct 2458 ms 664428 KB Output is correct
38 Correct 2623 ms 664204 KB Output is correct
39 Correct 2249 ms 642532 KB Output is correct
40 Correct 690 ms 145936 KB Output is correct
41 Correct 821 ms 152484 KB Output is correct
42 Correct 316 ms 7844 KB Output is correct
43 Correct 2652 ms 690896 KB Output is correct
44 Correct 2635 ms 691036 KB Output is correct
45 Correct 2947 ms 690820 KB Output is correct
46 Correct 1197 ms 353308 KB Output is correct
47 Correct 1199 ms 343092 KB Output is correct
48 Correct 381 ms 8920 KB Output is correct
49 Correct 2593 ms 658492 KB Output is correct
50 Correct 2490 ms 660112 KB Output is correct
51 Correct 2272 ms 626696 KB Output is correct
52 Correct 846 ms 192244 KB Output is correct
53 Correct 895 ms 195428 KB Output is correct