| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93429 |
2019-01-08T11:45:51 Z |
Bodo171 |
Game (IOI13_game) |
C++14 |
|
2 ms |
380 KB |
#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#include <ctime>
#include <cstdlib>
#define mp make_pair
using namespace std;
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;
}
static long long ans;
static int Rowss,Columnss;
static int X1,Y1,X2,Y2;
struct Treap
{
Treap *ls,*rs;
int pr,poz;
long long G,sub;
Treap()
{
ls=rs=0;
pr=rand()+1;
poz=0;
G=sub=0;
}
}*nil=new Treap;
void rec(Treap * &T)
{
if(T->ls&&T->rs)T->sub=gcd(T->ls->sub,T->rs->sub);
else T->sub=0;
T->sub=gcd(T->sub,T->G);
}
void rotl(Treap* &T)
{
Treap *aux=T;
T=T->ls;
aux->ls=T->rs;
T->rs=aux;
rec(T->rs);rec(T);
}
void rotr(Treap* &T)
{
Treap *aux=T;
T=T->rs;
aux->rs=T->ls;
T->ls=aux;
rec(T->ls);rec(T);
}
void updY(Treap* &T,int poz,long long value)
{
if(T->poz==poz)
{
T->G=value;
rec(T);
return;
}
if(T==nil)
{
T=new Treap;T->poz=poz;
T->ls=nil;T->rs=nil;
T->G=value;
rec(T);
return;
}
if(poz<T->poz) updY(T->ls,poz,value);
else updY(T->rs,poz,value);
if(T->ls->pr>T->pr) rotl(T);
else if(T->rs->pr>T->pr) rotr(T);
}
void qrY(Treap* &T,int l,int r)
{
if(T==nil) return;
if(T->poz>=Y1&&T->poz<=Y2)
{
ans=gcd(ans,T->G);
if(l>=Y1)
{
ans=gcd(T->ls->sub,ans);
}
else
{
qrY(T->ls,l,T->poz);
}
if(r<=Y2)
{
ans=gcd(T->rs->sub,ans);
}
else
{
qrY(T->rs,T->poz,r);
}
}
if(T->poz<Y1) qrY(T->rs,l,r);
if(T->poz>Y2) qrY(T->ls,l,r);
}
struct aint
{
aint *ls,*rs;
Treap *nxt;
aint()
{
ls=rs=0;nxt=0;
}
}*rad;
void init(int R, int C) {
Rowss=R;Columnss=C;
rad=new aint;
srand(time(NULL));
nil->pr=0;
}
long long aux=0;
void print(Treap* T)
{
if(T==nil)
return;
print(T->ls);
cout<<T->poz<<' '<<T->G<<' '<<T->pr<<'\n';
print(T->rs);
}
void updX(aint* &nod,int l,int r,int poz,int y,long long value)
{
if(!nod->nxt)
{
nod->nxt=nil;
}
if(l==r)
{
updY(nod->nxt,y,value);
return;
}
int m=(l+r)/2;
if(poz<=m)
{
if(!nod->ls) nod->ls=new aint;
updX(nod->ls,l,m,poz,y,value);
}
else
{
if(!nod->rs) nod->rs=new aint;
updX(nod->rs,m+1,r,poz,y,value);
}
ans=0;Y1=Y2=y;
if(nod->ls)qrY(nod->ls->nxt,0,Columnss+1);
aux=ans;ans=0;
if(nod->rs)qrY(nod->rs->nxt,0,Columnss+1);
updY(nod->nxt,y,gcd(aux,ans));
}
void qrX(aint* &nod,int l,int r)
{
if(X1<=l&&r<=X2)
{
if(nod->nxt) qrY(nod->nxt,1,Columnss);
return;
}
int m=(l+r)/2;
if(X1<=m&&nod->ls) qrX(nod->ls,l,m);
if(m<X2&&nod->rs) qrX(nod->rs,m+1,r);
}
void update(int P, int Q, long long K) {
P++,Q++;
updX(rad,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(rad,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 |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 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 |
248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
380 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 |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
