oj.uz

Submission #1013701

# Submission time Handle Problem Language Result Execution time Memory
1013701 2024-07-03T21:42:17 Z amirhoseinfar1385 Game (IOI13_game) C++17
0 / 100
 412 ms 13068 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;
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];
        return;
    }else if(u3==-1){
        gc[u1]=gc[u2];
        cl[u1]=cl[u2];
        cr[u1]=cr[u2];
        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||sd==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]);
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 412 ms 13068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6596 KB Output isn't correct
3 Halted 0 ms 0 KB -