Submission #909717

#TimeUsernameProblemLanguageResultExecution timeMemory
909717JakobZorzGame (IOI13_game)C++17
80 / 100
2709 ms256000 KiB
#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; int ch1,ch2; Tree1():val(0),ch1(-1),ch2(-1){} }; const int SIZE1=15000000; const int SIZE2=1000000; 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,int rl,int rr,int x,ll v){ if(node==-1){ if(v==0) return -1; node=num1++; } if(rl==rr-1){ trees1[node].val=v; return node; } int mid=(rl+rr)/2; if(x<mid){ trees1[node].ch1=tree1_set(trees1[node].ch1,rl,mid,x,v); }else{ trees1[node].ch2=tree1_set(trees1[node].ch2,mid,rr,x,v); } trees1[node].val=gcd2(tree1_get_val(trees1[node].ch1),tree1_get_val(trees1[node].ch2)); return node; } ll tree1_get(int node,int rl,int rr,int x1,int x2){ if(node==-1) return 0; if(x2<=rl||rr<=x1) return 0; if(x1<=rl&&rr<=x2) return trees1[node].val; int mid=(rl+rr)/2; return gcd2(tree1_get(trees1[node].ch1,rl,mid,x1,x2),tree1_get(trees1[node].ch2,mid,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,int x1,int x2){ if(node==-1) return 0; return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2); } int tree2_set(int node,int rl,int rr,int x,int 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; } int 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,int rl,int rr,int x1,int x2,int y1,int 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); int 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); }

Compilation message (stderr)

game.cpp: In constructor 'Tree2::Tree2()':
game.cpp:80:13: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
   80 |     int ch1,ch2;
      |             ^~~
game.cpp:79:9: warning:   'int Tree2::val' [-Wreorder]
   79 |     int val;
      |         ^~~
game.cpp:81:5: warning:   when initialized here [-Wreorder]
   81 |     Tree2():ch1(-1),ch2(-1),val(-1){}
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...