oj.uz

Submission #1013699

# Submission time Handle Problem Language Result Execution time Memory
1013699 2024-07-03T21:37:53 Z amirhoseinfar1385 Game (IOI13_game) C++17
100 / 100
 3877 ms 51156 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int ted=20000000;
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 1 ms 8636 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 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 8632 KB Output is correct
11 Correct 1 ms 6492 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 6492 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 449 ms 17108 KB Output is correct
5 Correct 355 ms 16976 KB Output is correct
6 Correct 384 ms 14676 KB Output is correct
7 Correct 382 ms 13140 KB Output is correct
8 Correct 325 ms 14436 KB Output is correct
9 Correct 383 ms 14280 KB Output is correct
10 Correct 360 ms 13908 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 6488 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 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 900 ms 18740 KB Output is correct
13 Correct 1192 ms 15188 KB Output is correct
14 Correct 449 ms 13628 KB Output is correct
15 Correct 1379 ms 15696 KB Output is correct
16 Correct 364 ms 18000 KB Output is correct
17 Correct 768 ms 16820 KB Output is correct
18 Correct 1014 ms 19284 KB Output is correct
19 Correct 1002 ms 19488 KB Output is correct
20 Correct 1082 ms 17232 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 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8632 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 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 6492 KB Output is correct
12 Correct 472 ms 17088 KB Output is correct
13 Correct 412 ms 17124 KB Output is correct
14 Correct 415 ms 14616 KB Output is correct
15 Correct 410 ms 14164 KB Output is correct
16 Correct 305 ms 14416 KB Output is correct
17 Correct 417 ms 14416 KB Output is correct
18 Correct 440 ms 13904 KB Output is correct
19 Correct 964 ms 18004 KB Output is correct
20 Correct 1226 ms 13644 KB Output is correct
21 Correct 394 ms 13876 KB Output is correct
22 Correct 1357 ms 13568 KB Output is correct
23 Correct 400 ms 16208 KB Output is correct
24 Correct 779 ms 15956 KB Output is correct
25 Correct 1167 ms 16468 KB Output is correct
26 Correct 1040 ms 17744 KB Output is correct
27 Correct 993 ms 17324 KB Output is correct
28 Correct 284 ms 30800 KB Output is correct
29 Correct 1004 ms 32596 KB Output is correct
30 Correct 3592 ms 25576 KB Output is correct
31 Correct 3452 ms 21476 KB Output is correct
32 Correct 315 ms 18172 KB Output is correct
33 Correct 492 ms 18432 KB Output is correct
34 Correct 473 ms 27336 KB Output is correct
35 Correct 596 ms 23380 KB Output is correct
36 Correct 979 ms 30472 KB Output is correct
37 Correct 811 ms 30548 KB Output is correct
38 Correct 861 ms 31060 KB Output is correct
39 Correct 689 ms 27984 KB Output is correct
40 Correct 1 ms 8540 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 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 8656 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 452 ms 19196 KB Output is correct
13 Correct 393 ms 18772 KB Output is correct
14 Correct 414 ms 16316 KB Output is correct
15 Correct 394 ms 16144 KB Output is correct
16 Correct 346 ms 14396 KB Output is correct
17 Correct 421 ms 16216 KB Output is correct
18 Correct 389 ms 15704 KB Output is correct
19 Correct 961 ms 18720 KB Output is correct
20 Correct 1238 ms 15192 KB Output is correct
21 Correct 388 ms 13648 KB Output is correct
22 Correct 1401 ms 15832 KB Output is correct
23 Correct 395 ms 21588 KB Output is correct
24 Correct 857 ms 16888 KB Output is correct
25 Correct 1177 ms 17688 KB Output is correct
26 Correct 1022 ms 17988 KB Output is correct
27 Correct 1029 ms 20772 KB Output is correct
28 Correct 299 ms 30800 KB Output is correct
29 Correct 899 ms 33776 KB Output is correct
30 Correct 3272 ms 25944 KB Output is correct
31 Correct 3165 ms 24400 KB Output is correct
32 Correct 285 ms 18368 KB Output is correct
33 Correct 382 ms 18256 KB Output is correct
34 Correct 407 ms 27472 KB Output is correct
35 Correct 550 ms 26540 KB Output is correct
36 Correct 833 ms 31576 KB Output is correct
37 Correct 722 ms 31828 KB Output is correct
38 Correct 738 ms 31316 KB Output is correct
39 Correct 330 ms 48720 KB Output is correct
40 Correct 1217 ms 51156 KB Output is correct
41 Correct 3877 ms 41044 KB Output is correct
42 Correct 3712 ms 33932 KB Output is correct
43 Correct 563 ms 45648 KB Output is correct
44 Correct 339 ms 18516 KB Output is correct
45 Correct 636 ms 29008 KB Output is correct
46 Correct 1089 ms 50000 KB Output is correct
47 Correct 1098 ms 49852 KB Output is correct
48 Correct 1055 ms 49336 KB Output is correct
49 Correct 1 ms 8536 KB Output is correct