제출 #909733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909733		JakobZorz	Game (IOI13_game)	C++17	0 / 100	48 ms	243296 KiB

game

#include"game.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;

const ll TREE_SIZE=1LL<<32;

ll gcd2(ll X,ll Y){
    ll tmp;
    while (X!=Y&&Y!=0){
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}

// ===============================================================
// ===============================================================
// ===============================================================

struct Tree1{
    ll val;
    int ch1,ch2,ch3,ch4;
    Tree1():val(0),ch1(-1),ch2(-1){}
};

const int SIZE1=10000000;
const int SIZE2=700000;

int num1;
Tree1 trees1[SIZE1];

ll tree1_get_val(int node){
    if(node==-1)
        return 0;
    return trees1[node].val;
}

int tree1_set(int node,ll rl,ll rr,ll x,ll v){
    if(node==-1){
        if(v==0)
            return -1;
        node=num1++;
    }
    
    if(rl==rr-1){
        trees1[node].val=v;
        return node;
    }
    
    ll mid1=rl+(rr-rl)/4;
    ll mid2=rl+(rr-rl)/2;
    ll mid3=rl+(rr-rl)/4*3;
    if(x<mid1){
        trees1[node].ch1=tree1_set(trees1[node].ch1,rl,mid1,x,v);
    }else if(x<mid2){
        trees1[node].ch2=tree1_set(trees1[node].ch2,mid1,mid2,x,v);
    }else if(x<mid3){
        trees1[node].ch3=tree1_set(trees1[node].ch3,mid2,mid3,x,v);
    }else{
        trees1[node].ch4=tree1_set(trees1[node].ch4,mid3,rr,x,v);
    }
    trees1[node].val=gcd2(gcd2(tree1_get_val(trees1[node].ch1),tree1_get_val(trees1[node].ch2)),gcd2(tree1_get_val(trees1[node].ch3),tree1_get_val(trees1[node].ch4)));
    return node;
}

ll tree1_get(int node,ll rl,ll rr,ll x1,ll x2){
    if(node==-1)
        return 0;
    if(x2<=rl||rr<=x1)
        return 0;
    if(x1<=rl&&rr<=x2)
        return trees1[node].val;
    ll mid1=rl+(rr-rl)/4;
    ll mid2=rl+(rr-rl)/2;
    ll mid3=rl+(rr-rl)/4*3;
    return gcd2(gcd2(tree1_get(trees1[node].ch1,rl,mid1,x1,x2),tree1_get(trees1[node].ch2,mid1,mid2,x1,x2)),gcd2(tree1_get(trees1[node].ch3,mid2,mid3,x1,x2),tree1_get(trees1[node].ch4,mid3,rr,x1,x2)));
}

// ===============================================================
// ===============================================================
// ===============================================================

struct Tree2{
    int val;
    int ch1,ch2;
    Tree2():ch1(-1),ch2(-1),val(-1){}
};

int num2;
Tree2 trees2[SIZE2];

ll tree2_get_val(int node,ll x1,ll x2){
    if(node==-1)
        return 0;
    return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
}

int tree2_set(int node,ll rl,ll rr,ll x,ll y,ll v){
    if(node==-1){
        if(v==0)
            return -1;
        node=num2++;
        if(num2>=SIZE2){
            cout<<"ERROR\n";
            exit(0);
        }
    }
    
    if(rl==rr-1){
        trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,v);
        return node;
    }
    
    ll mid=(rl+rr)/2;
    if(y<mid){
        trees2[node].ch1=tree2_set(trees2[node].ch1,rl,mid,x,y,v);
    }else{
        trees2[node].ch2=tree2_set(trees2[node].ch2,mid,rr,x,y,v);
    }
    ll val=gcd2(tree2_get_val(trees2[node].ch1,x,x+1),tree2_get_val(trees2[node].ch2,x,x+1));
    trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,val);
    return node;
}

ll tree2_get(int node,ll rl,ll rr,ll x1,ll x2,ll y1,ll y2){
    if(node==-1)
        return 0;
    if(y2<=rl||rr<=y1)
        return 0;
    if(y1<=rl&&rr<=y2)
        return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
    ll mid=(rl+rr)/2;
    return gcd2(tree2_get(trees2[node].ch1,rl,mid,x1,x2,y1,y2),tree2_get(trees2[node].ch2,mid,rr,x1,x2,y1,y2));
}

// ===============================================================
// ===============================================================
// ===============================================================

void init(int h,int w){
    num2=1;
}

void update(int y,int x,ll v){
    tree2_set(0,0,TREE_SIZE,x,y,v);
}

ll calculate(int y1,int x1,int y2,int x2){
    return tree2_get(0,0,TREE_SIZE,x1,x2+1,y1,y2+1);
}

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

game.cpp: In constructor 'Tree2::Tree2()':
game.cpp:88:13: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
   88 |     int ch1,ch2;
      |             ^~~
game.cpp:87:9: warning:   'int Tree2::val' [-Wreorder]
   87 |     int val;
      |         ^~~
game.cpp:89:5: warning:   when initialized here [-Wreorder]
   89 |     Tree2():ch1(-1),ch2(-1),val(-1){}
      |     ^~~~~

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