oj.uz

Submission #1013703

# Submission time Handle Problem Language Result Execution time Memory
1013703 2024-07-03T21:44:34 Z amirhoseinfar1385 Game (IOI13_game) C++17
100 / 100
 4115 ms 49952 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];
    }else if(u3==-1){
        gc[u1]=gc[u2];
    }else{
        gc[u1]=gcd(gc[u2],gc[u3]);
    }
    if(l==r){
        return;
    }
    int sd=0;
    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 if((cl[u1]==cl[u2]&&cl[u1]!=-1)||(cl[u1]==cl[u3]&&cl[u1]!=-1)||(cr[u1]==cr[u2]&&cr[u1]!=-1)||(cr[u1]==cr[u3]&&cr[u1]!=-1)){
        cl[u1]=cr[u1]=-1;
        gc[u1]=gcd(gc[u2],gc[u3]);
        sd=1;
    }
    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);
}

Compilation message

game.cpp: In function 'void asl(int, int, int, int, int, int, int)':
game.cpp:96:9: warning: variable 'sd' set but not used [-Wunused-but-set-variable]
   96 |     int sd=0;
      |         ^~

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 2 ms 8644 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 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 1 ms 8540 KB Output is correct

Subtask #2
27.0 / 27.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 8540 KB Output is correct
4 Correct 435 ms 12648 KB Output is correct
5 Correct 330 ms 15132 KB Output is correct
6 Correct 393 ms 12368 KB Output is correct
7 Correct 433 ms 11856 KB Output is correct
8 Correct 316 ms 12512 KB Output is correct
9 Correct 419 ms 12128 KB Output is correct
10 Correct 375 ms 11604 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct

Subtask #3
26.0 / 26.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 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 1018 ms 16900 KB Output is correct
13 Correct 1233 ms 11660 KB Output is correct
14 Correct 394 ms 11604 KB Output is correct
15 Correct 1407 ms 13924 KB Output is correct
16 Correct 368 ms 13652 KB Output is correct
17 Correct 851 ms 14500 KB Output is correct
18 Correct 1046 ms 14388 KB Output is correct
19 Correct 997 ms 14580 KB Output is correct
20 Correct 1000 ms 14088 KB Output is correct
21 Correct 1 ms 8540 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 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8536 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 471 ms 15172 KB Output is correct
13 Correct 326 ms 15308 KB Output is correct
14 Correct 365 ms 12116 KB Output is correct
15 Correct 389 ms 11856 KB Output is correct
16 Correct 309 ms 12372 KB Output is correct
17 Correct 413 ms 12116 KB Output is correct
18 Correct 389 ms 11600 KB Output is correct
19 Correct 931 ms 16992 KB Output is correct
20 Correct 1265 ms 11432 KB Output is correct
21 Correct 359 ms 11712 KB Output is correct
22 Correct 1442 ms 13956 KB Output is correct
23 Correct 391 ms 13648 KB Output is correct
24 Correct 817 ms 14424 KB Output is correct
25 Correct 1137 ms 14464 KB Output is correct
26 Correct 1012 ms 14560 KB Output is correct
27 Correct 1002 ms 14048 KB Output is correct
28 Correct 286 ms 25052 KB Output is correct
29 Correct 847 ms 27808 KB Output is correct
30 Correct 3522 ms 23324 KB Output is correct
31 Correct 3450 ms 21480 KB Output is correct
32 Correct 289 ms 13908 KB Output is correct
33 Correct 390 ms 13908 KB Output is correct
34 Correct 416 ms 23112 KB Output is correct
35 Correct 540 ms 21096 KB Output is correct
36 Correct 889 ms 25572 KB Output is correct
37 Correct 783 ms 25780 KB Output is correct
38 Correct 778 ms 25168 KB Output is correct
39 Correct 680 ms 23380 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 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 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 435 ms 15200 KB Output is correct
13 Correct 375 ms 15440 KB Output is correct
14 Correct 374 ms 12116 KB Output is correct
15 Correct 434 ms 11856 KB Output is correct
16 Correct 304 ms 12996 KB Output is correct
17 Correct 394 ms 11892 KB Output is correct
18 Correct 395 ms 11824 KB Output is correct
19 Correct 941 ms 17092 KB Output is correct
20 Correct 1132 ms 11608 KB Output is correct
21 Correct 410 ms 11588 KB Output is correct
22 Correct 1466 ms 13780 KB Output is correct
23 Correct 401 ms 13648 KB Output is correct
24 Correct 743 ms 14432 KB Output is correct
25 Correct 1010 ms 14416 KB Output is correct
26 Correct 1037 ms 14532 KB Output is correct
27 Correct 999 ms 14004 KB Output is correct
28 Correct 356 ms 25168 KB Output is correct
29 Correct 879 ms 27944 KB Output is correct
30 Correct 3352 ms 23300 KB Output is correct
31 Correct 3063 ms 21448 KB Output is correct
32 Correct 273 ms 13908 KB Output is correct
33 Correct 389 ms 13904 KB Output is correct
34 Correct 442 ms 23120 KB Output is correct
35 Correct 578 ms 21100 KB Output is correct
36 Correct 945 ms 25440 KB Output is correct
37 Correct 773 ms 25752 KB Output is correct
38 Correct 783 ms 25172 KB Output is correct
39 Correct 343 ms 47764 KB Output is correct
40 Correct 1132 ms 49952 KB Output is correct
41 Correct 4115 ms 39956 KB Output is correct
42 Correct 3672 ms 31524 KB Output is correct
43 Correct 566 ms 40736 KB Output is correct
44 Correct 364 ms 14104 KB Output is correct
45 Correct 709 ms 23304 KB Output is correct
46 Correct 1063 ms 45260 KB Output is correct
47 Correct 1156 ms 47412 KB Output is correct
48 Correct 1113 ms 46944 KB Output is correct
49 Correct 1 ms 8540 KB Output is correct