oj.uz

Submission #1013704

# Submission time Handle Problem Language Result Execution time Memory
1013704 2024-07-03T21:46:10 Z amirhoseinfar1385 Game (IOI13_game) C++17
100 / 100
 3902 ms 48196 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int ted=10000000;
int kaf=1000000000+1;
int n,m;
long long gcd(long long a,long long b){
    if(a==0){
        return b;
    }
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
long long gc[ted];
int cl[ted],cr[ted];
bitset<ted>lnk,vas;
int te;
 
void gotime(){
    int z=1e6;
    for(int i=0;i<100000000000;i++){
        z=sqrt(z);
        z+=23476;
    }
    cout<<z<<endl;
}
 
void init(int R, int C) {
    //hehe
    te=2;
    cl[0]=cl[1]=cr[0]=cr[1]=-1;
    lnk[0]=1;
}
 
int getr(int u){
    if(cr[u]==-1){
        if(lnk[u]==0){
            cr[u]=te;
            cl[te]=cr[te]=-1;
            te++;
        }else{
            cr[u]=te;
            lnk[te]=1;
            cl[te]=cr[te]=-1;
            cl[te+1]=cr[te+1]=-1;
            te+=2;
        }
    }
    if(te>=ted){
        gotime();
    }
    return cr[u];
}
 
int getl(int u){
    if(cl[u]==-1){
        if(lnk[u]==0){
            cl[u]=te;
            cl[te]=cr[te]=-1;
            te++;
        }else{
            cl[u]=te;
            lnk[te]=1;
            cl[te]=cr[te]=-1;
            cl[te+1]=cr[te+1]=-1;
            te+=2;
        }
    }
    if(te>=ted){
         gotime();
    }
    return cl[u];
}
 
void asl(int u1,int u2,int u3,int l,int r,int tr,int hey=0){
    if((l>r||!(tr>=l&&tr<=r))&&hey==0){
        return ;
    }
    if(u2==-1&&u3==-1){
        gc[u1]=0;
        cl[u1]=cr[u1]=-1;
        return ;
    }
    else if(u2==-1){
        gc[u1]=gc[u3];
        cl[u1]=cl[u3];
        cr[u1]=cr[u3];
        vas[u1]=1;
        return;
    }else if(u3==-1){
        gc[u1]=gc[u2];
        cl[u1]=cl[u2];
        cr[u1]=cr[u2];
        vas[u1]=1;
        return ;
    }else{
        gc[u1]=gcd(gc[u2],gc[u3]);
    }
    if(l==r){
        return;
    }
    int m=(l+r)>>1;
    int l2,l3,r2,r3;
    if(u2==-1||cl[u2]==-1){
        l2=-1;
    }else{
        l2=cl[u2];
    }
    if(u3==-1||cl[u3]==-1){
        l3=-1;
    }else{
        l3=cl[u3];
    }
 
 
    if(u2==-1||cr[u2]==-1){
        r2=-1;
    }else{
        r2=cr[u2];
    }
    if(u3==-1||cr[u3]==-1){
        r3=-1;
    }else{
        r3=cr[u3];
    }
    if(hey==1||vas[u1]==1){
        cl[u1]=cr[u1]=-1;
        asl(getl(u1),l2,l3,l,m,tr,1);
        asl(getr(u1),r2,r3,m+1,r,tr,1);
        gc[u1]=gcd(gc[u2],gc[u3]);
        vas[u1]=0;
        return ;
    }
    if(tr<=m){
       /* if(l2==-1){
            cl[u1]=l3;
            return ;
        }
        if(l3==-1){
            cl[u1]=l2;
            return ;
        }
        if(cl[u1]==l2||cl[u1]==l3){
            cl[u1]=-1;
        }*/
        asl(getl(u1),l2,l3,l,m,tr,hey);
    }else{
        /*if(r2==-1){
            cr[u1]=r3;
            return ;
        }
        if(r3==-1){
            cr[u1]=r2;
            return ;
        }
        if(cr[u1]==r2||cr[u1]==r3){
            cr[u1]=-1;
        }*/
       asl(getr(u1),r2,r3,m+1,r,tr,hey);
    }
}
 
void calc(int u,int tr){
    if(lnk[u]==0){
        return ;
    }
    int cll=cl[u];
    int crr=cr[u];
    if(cll==-1){
        cll=-2;
    }
    if(crr==-1){
        crr=-2;
    }
    asl(u+1,cll+1,crr+1,0,kaf-1,tr);
}
 
void upd(int u,int l,int r,int tl,int tr,long long w){
    if(l>r||l>tl||r<tl){
        return ;
    }
    if(l==r){
        if(lnk[u]==0){
            gc[u]=w;
        }else{
            upd(u+1,0,kaf-1,tr,tl,w);
        }
        return ;
    }
    int m=(l+r)>>1;
    if(tl<=m){
        upd(getl(u),l,m,tl,tr,w);
    }else{
        upd(getr(u),m+1,r,tl,tr,w);
    }
    if(lnk[u]==1){
        calc(u,tr);
    }else{
        if(cl[u]==-1){
            gc[u]=gc[cr[u]];
        }else if(cr[u]==-1){
            gc[u]=gc[cl[u]];
        }else{
            gc[u]=gcd(gc[getl(u)],gc[getr(u)]);
        }
    }
}
 
long long pors(int u,int l,int r,int tl,int tr,int tl2,int tr2){
    if(u==-1||l>r||l>tr||r<tl||tl>tr){
        return 0;
    }
    if(l>=tl&&r<=tr){
        if(lnk[u]==0){
            return gc[u];
        }else{
            return pors(u+1,0,kaf-1,tl2,tr2,tl,tr);
        }
    }
    int m=(l+r)>>1;
    return gcd(pors(cl[u],l,m,tl,tr,tl2,tr2),pors(cr[u],m+1,r,tl,tr,tl2,tr2));
}
 
void update(int P,int Q, long long K) {
    upd(0,0,kaf-1,P,Q,K);
}
 
long long calculate(int P,int Q,int U,int V) {
    return pors(0,0,kaf-1,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8536 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8636 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 471 ms 16716 KB Output is correct
5 Correct 369 ms 16464 KB Output is correct
6 Correct 403 ms 14008 KB Output is correct
7 Correct 428 ms 13612 KB Output is correct
8 Correct 329 ms 13908 KB Output is correct
9 Correct 426 ms 13880 KB Output is correct
10 Correct 366 ms 13332 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8656 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8632 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8644 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1022 ms 18364 KB Output is correct
13 Correct 1186 ms 12904 KB Output is correct
14 Correct 390 ms 13476 KB Output is correct
15 Correct 1394 ms 15444 KB Output is correct
16 Correct 411 ms 15184 KB Output is correct
17 Correct 795 ms 16180 KB Output is correct
18 Correct 1076 ms 16572 KB Output is correct
19 Correct 1002 ms 16724 KB Output is correct
20 Correct 997 ms 15952 KB Output is correct
21 Correct 1 ms 8536 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8632 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 484 ms 16752 KB Output is correct
13 Correct 351 ms 16464 KB Output is correct
14 Correct 379 ms 13908 KB Output is correct
15 Correct 383 ms 13564 KB Output is correct
16 Correct 284 ms 13908 KB Output is correct
17 Correct 375 ms 13904 KB Output is correct
18 Correct 400 ms 13360 KB Output is correct
19 Correct 853 ms 18216 KB Output is correct
20 Correct 1156 ms 12836 KB Output is correct
21 Correct 367 ms 13396 KB Output is correct
22 Correct 1279 ms 15444 KB Output is correct
23 Correct 346 ms 15148 KB Output is correct
24 Correct 768 ms 16340 KB Output is correct
25 Correct 1006 ms 16252 KB Output is correct
26 Correct 904 ms 16464 KB Output is correct
27 Correct 919 ms 15892 KB Output is correct
28 Correct 254 ms 28236 KB Output is correct
29 Correct 809 ms 30640 KB Output is correct
30 Correct 3230 ms 25248 KB Output is correct
31 Correct 3124 ms 23408 KB Output is correct
32 Correct 272 ms 16468 KB Output is correct
33 Correct 405 ms 16484 KB Output is correct
34 Correct 404 ms 25568 KB Output is correct
35 Correct 563 ms 24084 KB Output is correct
36 Correct 891 ms 28752 KB Output is correct
37 Correct 782 ms 28904 KB Output is correct
38 Correct 782 ms 28364 KB Output is correct
39 Correct 702 ms 26664 KB Output is correct
40 Correct 1 ms 8536 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 484 ms 16612 KB Output is correct
13 Correct 366 ms 16520 KB Output is correct
14 Correct 376 ms 13908 KB Output is correct
15 Correct 422 ms 13648 KB Output is correct
16 Correct 307 ms 13904 KB Output is correct
17 Correct 374 ms 13888 KB Output is correct
18 Correct 379 ms 13392 KB Output is correct
19 Correct 950 ms 18212 KB Output is correct
20 Correct 1207 ms 12944 KB Output is correct
21 Correct 380 ms 13472 KB Output is correct
22 Correct 1391 ms 15444 KB Output is correct
23 Correct 358 ms 15188 KB Output is correct
24 Correct 799 ms 16468 KB Output is correct
25 Correct 1022 ms 16464 KB Output is correct
26 Correct 939 ms 16328 KB Output is correct
27 Correct 896 ms 15956 KB Output is correct
28 Correct 288 ms 28448 KB Output is correct
29 Correct 831 ms 30768 KB Output is correct
30 Correct 3347 ms 25268 KB Output is correct
31 Correct 3378 ms 23380 KB Output is correct
32 Correct 319 ms 16464 KB Output is correct
33 Correct 455 ms 16504 KB Output is correct
34 Correct 449 ms 25428 KB Output is correct
35 Correct 624 ms 23888 KB Output is correct
36 Correct 867 ms 28496 KB Output is correct
37 Correct 727 ms 28756 KB Output is correct
38 Correct 696 ms 28144 KB Output is correct
39 Correct 316 ms 45072 KB Output is correct
40 Correct 1145 ms 48196 KB Output is correct
41 Correct 3902 ms 39248 KB Output is correct
42 Correct 3634 ms 32844 KB Output is correct
43 Correct 536 ms 43856 KB Output is correct
44 Correct 329 ms 18260 KB Output is correct
45 Correct 674 ms 27936 KB Output is correct
46 Correct 1008 ms 44372 KB Output is correct
47 Correct 1026 ms 43092 KB Output is correct
48 Correct 969 ms 42832 KB Output is correct
49 Correct 1 ms 8540 KB Output is correct