# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
93146 |
2019-01-06T15:16:24 Z |
Bodo171 |
Game (IOI13_game) |
C++14 |
|
2 ms |
548 KB |
#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#define mp make_pair
using namespace std;
struct aint
{
aint *ls,*rs,*nxt;
long long val;
bool ok;
aint()
{
ls=rs=0;nxt=0;
val=0;ok=0;
}
};
static aint *rad,*arb[40005];
static long long ans;
static int Rowss,Columnss;
static int X1,Y1,X2,Y2;
long long gcd(long long X, long long Y) {
long long tmp;
if(!X) return Y;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void init(int R, int C) {
Rowss=R;Columnss=C;
for(int i=1;i<=4*R;i++)
arb[i]=new aint;
rad=new aint;
}
void updY(aint* &nod,int l,int r,int poz,long long value)
{
if(l==r)
{
nod->val=value;
return;
}
int m=(l+r)/2;
if(poz<=m)
{
if(!nod->ls) nod->ls=new aint;
updY(nod->ls,l,m,poz,value);
}
else
{
if(!nod->rs) nod->rs=new aint;
updY(nod->rs,m+1,r,poz,value);
}
nod->val=0;
if(nod->ls) nod->val=gcd(nod->val,nod->ls->val);
if(nod->rs) nod->val=gcd(nod->val,nod->rs->val);
}
void updX(int nod,int l,int r,int poz,int y,long long value)
{
updY(arb[nod],1,Columnss,y,value);
if(l==r) return;
int m=(l+r)/2;
if(poz<=m) updX(2*nod,l,m,poz,y,value);
else updX(2*nod+1,m+1,r,poz,y,value);
}
void qrY(aint* &nod,int l,int r)
{
if(Y1<=l&&r<=Y2)
{
ans=1LL*gcd(ans,nod->val);
return;
}
int m=(l+r)/2;
if(Y1<=m&&nod->ls) qrY(nod->ls,l,m);
if(m<Y2&&nod->rs) qrY(nod->rs,m+1,r);
}
void qrX(int nod,int l,int r)
{
if(X1<=l&&r<=X2)
{
qrY(arb[nod],1,Columnss);
return;
}
int m=(l+r)/2;
if(X1<=m) qrX(2*nod,l,m);
if(m<X2) qrX(2*nod+1,m+1,r);
}
void update(int P, int Q, long long K) {
P++,Q++;
updX(1,1,Rowss,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
ans=0;
P++,Q++,U++,V++;
X1=P;Y1=Q;X2=U;Y2=V;
qrX(1,1,Rowss);
return ans;
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
420 KB |
Output is correct |
2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
424 KB |
Output is correct |
2 |
Incorrect |
2 ms |
548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |