| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 293831 |
2020-09-08T12:50:52 Z |
AMO5 |
Game (IOI13_game) |
C++17 |
|
295 ms |
256004 KB |
#include <bits/stdc++.h>
#include "game.h"
//modified from ainta'solution
using namespace std;
int R,C;
long long gcd(long long a, long long b){
while(a!=b&&b!=0){
swap(a,b);
b=b%a;
}
return a;
}
struct vrt{
vrt *cl,*cr;
long long val;
int k;
vrt(int kk){
cl=cr=NULL;
k=kk;
val=0ll;
}
};
struct hor{
hor *cl,*cr;
vrt *cy;
long long val;
};
hor *root;
void init(int r, int c){
R=r; C=c;
root = new hor();
}
void updv(int pos, long long v, vrt *node, int le, int ri){
//cerr<<le<<"-"<<ri<<":"<<pos<<" "<<v<<"\n";
int mid=(le+ri)>>1;
if(node->k){
//cerr<<node->k<<"\n";
if(node->k==pos){
node->val=v;
//cerr<<"ret \n";
return;
}
if(node->k<=pos)node->cl=new vrt(node->k),node->cl->val=node->val;
else node->cr=new vrt(node->k),node->cr->val=node->val;
node->k=0;
}
if(pos<=mid){
if(!node->cl)node->cl=new vrt(pos);
updv(pos,v,node->cl,le,mid);
}else{
if(!node->cr)node->cr=new vrt(pos);
updv(pos,v,node->cr,mid+1,ri);
}
//cerr<<"okay \n";
node->val=gcd((node->cl?node->cl->val:0),(node->cr?node->cr->val:0));
}
long long get(vrt *node, int y, int le, int ri){
//cerr<<" get "<<le<<"-"<<ri<<" "<<y<<"\n";
if(node==NULL)return 0;
if(node->k){
//cerr<<node->k<<" "<<node->val<<"\n";
if(node->k==y)return node->val;
return 0;
}
int mid=(le+ri)>>1;
if(y<=mid)return get(node->cl,y,le,mid);
else return get(node->cr,y,mid+1,ri);
}
void updh(int x, int y, long long v, hor *node, int le, int ri){
//cerr<<le<<" "<<ri<<" "<<x<<" "<<y<<" "<<v<<"\n";
if(!node->cy){
node->cy=new vrt(y);
}
if(le==ri){
updv(y,v,node->cy,1,C);
return;
}
int mid=(le+ri)>>1;
if(!node->cl)node->cl=new hor();
if(!node->cr)node->cr=new hor();
if(x<=mid)updh(x,y,v,node->cl,le,mid);
else updh(x,y,v,node->cr,mid+1,ri);
//cerr<<" okay "<<"\n";
long long r=0ll;
r=gcd(get(node->cl->cy,y,1,C),r);
//cerr<<"left done\n";
r=gcd(get(node->cr->cy,y,1,C),r);
//cerr<<"right done\n";
updv(y,r,node->cy,1,C);
}
void update(int p, int q, long long k){
p++; q++;
updh(p,q,k,root,1,R);
}
long long dnc(int x, int y, vrt *node, int le, int ri){
if(node==NULL)return 0ll;
if(x>ri||le>y)return 0ll;
if(node->k){
int pos = node->k;
if(x<=pos&&pos<=y)return node->val;
return 0ll;
}
int mid=(le+ri)>>1;
long long r = 0ll;
r = gcd(r,dnc(x,y,node->cl,le,mid));
r = gcd(r,dnc(x,y,node->cr,mid+1,ri));
return r;
}
long long solve(int p, int q, int u, int v, hor *node, int le, int ri){
//cerr<<le<<"-"<<ri<<" "<<p<<" "<<q<<" "<<u<<" "<<v<<"\n";
if(p>ri||le>u)return 0ll;
if(p<=le&&ri<=u)return dnc(q,v,node->cy,1,C);
int mid=(le+ri)>>1;
long long r = 0ll;
if(node->cl)r = gcd(r,solve(p,q,u,v,node->cl,le,mid));
if(node->cr)r = gcd(r,solve(p,q,u,v,node->cr,mid+1,ri));
return r;
}
long long calculate(int p, int q, int u, int v){
p++; q++; u++; v++;
return solve(p,q,u,v,root,1,R);
}
/*
int main(){
//ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int r,c,q;
cin>>r>>c>>q;
init(r,c);
int t,x,y,x2,y2;
long long v;
for(int i=0; i<q; i++){
cin>>t;
//cerr<<i<<" qu "<<t<<"\n";
if(t==1){
cin>>x>>y>>v;
update(x,y,v);
}else{
cin>>x>>y>>x2>>y2;
cout<<calculate(x,y,x2,y2)<<"\n";
}
}
return 0;
}
*/
Compilation message
grader.c: In function 'int main()':
grader.c:25:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
25 | while(res != 1);
| ^~~~~
grader.c:26:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
26 | res = fscanf(f, "%d", &C);
| ^~~
grader.c:27:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
27 | while(res != 1);
| ^~~~~
grader.c:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
28 | res = fscanf(f, "%d", &N);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
203 ms |
256004 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Runtime error |
246 ms |
256004 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
283 ms |
256004 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
295 ms |
256004 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
216 ms |
256004 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
