제출 #909668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909668		JakobZorz	게임 (IOI13_game)	C++17	63 / 100	2173 ms	256000 KiB

game

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

const int TREE_SIZE=1<<30;

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;
    Tree1*ch1,*ch2;
    Tree1():val(0),ch1(0),ch2(0){}
};

ll tree1_get_val(Tree1*node){
    if(node==nullptr)
        return 0;
    return node->val;
}

Tree1*tree1_set(Tree1*node,int rl,int rr,int x,ll v){
    if(node==nullptr)
        node=new Tree1;
    
    if(rl==rr-1){
        node->val=v;
        return node;
    }
    
    int mid=(rl+rr)/2;
    if(x<mid){
        node->ch1=tree1_set(node->ch1,rl,mid,x,v);
    }else{
        node->ch2=tree1_set(node->ch2,mid,rr,x,v);
    }
    node->val=gcd2(tree1_get_val(node->ch1),tree1_get_val(node->ch2));
    return node;
}

ll tree1_get(Tree1*node,int rl,int rr,int x1,int x2){
    if(node==nullptr)
        return 0;
    if(x2<=rl||rr<=x1)
        return 0;
    if(x1<=rl&&rr<=x2)
        return node->val;
    int mid=(rl+rr)/2;
    return gcd2(tree1_get(node->ch1,rl,mid,x1,x2),tree1_get(node->ch2,mid,rr,x1,x2));
}

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

struct Tree2{
    Tree1*val;
    Tree2*ch1,*ch2;
    Tree2():ch1(0),ch2(0),val(0){}
};

ll tree2_get_val(Tree2*node,int x1,int x2){
    if(node==nullptr)
        return 0;
    return tree1_get(node->val,0,TREE_SIZE,x1,x2);
}

Tree2*tree2_set(Tree2*node,int rl,int rr,int x,int y,ll v){
    if(node==nullptr)
        node=new Tree2;
    
    if(rl==rr-1){
        node->val=tree1_set(node->val,0,TREE_SIZE,x,v);
        return node;
    }
    
    int mid=(rl+rr)/2;
    if(y<mid){
        node->ch1=tree2_set(node->ch1,rl,mid,x,y,v);
    }else{
        node->ch2=tree2_set(node->ch2,mid,rr,x,y,v);
    }
    ll val=gcd2(tree2_get_val(node->ch1,x,x+1),tree2_get_val(node->ch2,x,x+1));
    node->val=tree1_set(node->val,0,TREE_SIZE,x,val);
    return node;
}

ll tree2_get(Tree2*node,int rl,int rr,int x1,int x2,int y1,int y2){
    if(node==nullptr)
        return 0;
    if(y2<=rl||rr<=y1)
        return 0;
    if(y1<=rl&&rr<=y2)
        return tree1_get(node->val,0,TREE_SIZE,x1,x2);
    int mid=(rl+rr)/2;
    return gcd2(tree2_get(node->ch1,rl,mid,x1,x2,y1,y2),tree2_get(node->ch2,mid,rr,x1,x2,y1,y2));
}

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

Tree2 tree;

void init(int h,int w){
    
}

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

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

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

game.cpp: In constructor 'Tree2::Tree2()':
game.cpp:71:16: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
   71 |     Tree2*ch1,*ch2;
      |                ^~~
game.cpp:70:11: warning:   'Tree1* Tree2::val' [-Wreorder]
   70 |     Tree1*val;
      |           ^~~
game.cpp:72:5: warning:   when initialized here [-Wreorder]
   72 |     Tree2():ch1(0),ch2(0),val(0){}
      |     ^~~~~

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