제출 #1013249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013249		amirhoseinfar1385	게임 (IOI13_game)	C++17	80 / 100	3357 ms	256008 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int ted=14050000;
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);
}
 
struct node{
    int cl,cr;
    long long gc;
    node(){
        cl=cr=-1;
        gc=0;
    }
}fake;
node allnode[ted];
bitset<ted>lnk;
int te;
 
void init(int R, int C) {
    //hehe
    te=2;
    lnk[0]=1;
}
 
int getr(int u){
    if(allnode[u].cr==-1){
        if(lnk[u]==0){
            allnode[u].cr=te;
            te++;
        }else{
            allnode[u].cr=te;
            lnk[te]=1;
            te+=2;
        }
    }
    if(te>=ted){
        assert(0);
    }
    return allnode[u].cr;
}
 
int getl(int u){
    if(allnode[u].cl==-1){
        if(lnk[u]==0){
            allnode[u].cl=te;
            te++;
        }else{
            allnode[u].cl=te;
            lnk[te]=1;
            te+=2;
        }
    }
    if(te>=ted){
        assert(0);
    }
    return allnode[u].cl;
}
 
void asl(int u1,int u2,int u3,int l,int r,int tr){
    if(l>r||!(tr>=l&&tr<=r)){
        return ;
    }
    if(u2==-1){
        allnode[u1].gc=allnode[u3].gc;
    }else if(u3==-1){
        allnode[u1].gc=allnode[u2].gc;
    }else{
        allnode[u1].gc=gcd(allnode[u2].gc,allnode[u3].gc);
    }
    if(l==r){
        return;
    }
    int m=(l+r)>>1;
    int l1,l2,l3,r1,r2,r3;
    if(u2==-1||allnode[u2].cl==-1){
        l2=-1;
    }else{
        l2=allnode[u2].cl;
    }
    if(u3==-1||allnode[u3].cl==-1){
        l3=-1;
    }else{
        l3=allnode[u3].cl;
    }
 
 
    if(u2==-1||allnode[u2].cr==-1){
        r2=-1;
    }else{
        r2=allnode[u2].cr;
    }
    if(u3==-1||allnode[u3].cr==-1){
        r3=-1;
    }else{
        r3=allnode[u3].cr;
    }
    if(tr<=m){
        asl(getl(u1),l2,l3,l,m,tr);
    }else{
       asl(getr(u1),r2,r3,m+1,r,tr);
    }
}
 
void calc(int u,int tr){
    if(lnk[u]==0){
        return ;
    }
    int cl=allnode[u].cl;
    int cr=allnode[u].cr;
    asl(u+1,cl+1,cr+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){
            allnode[u].gc=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{
        //allnode[u].gc=gcd(allnode[getl(u)].gc,allnode[getr(u)].gc);
        if(allnode[u].cl==-1){
            allnode[u].gc=allnode[allnode[u].cr].gc;
        }else if(allnode[u].cr==-1){
            allnode[u].gc=allnode[allnode[u].cl].gc;
        }else{
            allnode[u].gc=gcd(allnode[getl(u)].gc,allnode[getr(u)].gc);
        }
    }
}
 
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 allnode[u].gc;
        }else{
            return pors(u+1,0,kaf-1,tl2,tr2,tl,tr);
        }
    }
    int m=(l+r)>>1;
    return gcd(pors(allnode[u].cl,l,m,tl,tr,tl2,tr2),pors(allnode[u].cr,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);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void asl(int, int, int, int, int, int)':
game.cpp:84:9: warning: unused variable 'l1' [-Wunused-variable]
   84 |     int l1,l2,l3,r1,r2,r3;
      |         ^~
game.cpp:84:18: warning: unused variable 'r1' [-Wunused-variable]
   84 |     int l1,l2,l3,r1,r2,r3;
      |                  ^~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20