| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4627 |
2013-11-13T11:03:41 Z |
ainta |
Game (IOI13_game) |
C++ |
|
0 ms |
1204 KB |
#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
int N,M;
struct Y_Seg{
Y_Seg *c1, *c2;
int b,e;
long long G;
Y_Seg(int p,int q){
c1=NULL,c2=NULL,G=0;
b=p,e=q;
}
};
struct X_Seg{
X_Seg *c1, *c2;
Y_Seg *cy;
int b,e;
X_Seg(int p,int q){
c1=NULL,c2=NULL,cy=NULL;
b=p,e=q;
}
};
X_Seg *root;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void init(int R, int C) {
N=R,M=C;
root = new X_Seg(0,N-1);
}
void update_Y(Y_Seg *node, int y, long long K){
if(node->b==node->e){
node->G=K;
return;
}
int m = (node->b+node->e)>>1;
if(!node->c1)node->c1 = new Y_Seg(node->b,m);
if(!node->c2)node->c2 = new Y_Seg(m+1,node->e);
if(m < y)update_Y(node->c2, y, K);
else update_Y(node->c1, y, K);
node->G=gcd2(node->c1->G,node->c2->G);
}
void update_XY(X_Seg *node, int y){
Y_Seg *n1=node->c1->cy, *n2=node->c2->cy, *cur=node->cy;
int m;
while(n1 || n2){
cur->G = gcd2(n1?n1->G:0,n2?n2->G:0);
if(cur->b==cur->e)break;
m=(cur->b+cur->e)>>1;
if(!cur->c1)cur->c1=new Y_Seg(cur->b,m);
if(!cur->c2)cur->c2=new Y_Seg(m+1,cur->e);
if(m<=y){
cur=cur->c1;
if(n1)n1=n1->c1;
if(n2)n2=n2->c1;
}
else{
cur=cur->c2;
if(n1)n1=n1->c2;
if(n2)n2=n2->c2;
}
}
}
void update_X(X_Seg *node, int x, int y, long long K){
if(node->b==node->e){
if(node->cy==NULL)node->cy = new Y_Seg(0,M-1);
update_Y(node->cy, y, K);
return;
}
int m = (node->b+node->e)>>1;
if(!node->c1)node->c1 = new X_Seg(node->b,m);
if(!node->c2)node->c2 = new X_Seg(m+1,node->e);
if(!node->cy)node->cy = new Y_Seg(0,M-1);
if(m < x)update_X(node->c2, x, y, K);
else update_X(node->c1, x, y, K);
update_XY(node, y);
}
void update(int P, int Q, long long K) {
update_X(root,P,Q,K);
}
long long CalcY(Y_Seg *node, int s,int l){
if(s==node->b && l==node->e){
return node->G;
}
int m = (node->b + node->e) >>1;
long long G=0;
if(s <= m){
if(node->c1)G=CalcY(node->c1,s,min(l,m));
}
if(l > m){
if(node->c2)G=gcd2(G,CalcY(node->c2,max(m+1,s),l));
}
return G;
}
long long CalcX(X_Seg *node, int P,int Q,int U,int V){
if(P==node->b && U==node->e){
return CalcY(node->cy,Q,V);
}
int m = (node->b + node->e) >>1;
long long G=0;
if(P <= m){
if(node->c1)G=CalcX(node->c1,P,Q,min(U,m),V);
}
if(U > m){
if(node->c2)G=gcd2(G,CalcX(node->c2,max(m+1,P),Q,U,V));
}
return G;
}
long long calculate(int P, int Q, int U, int V) {
return CalcX(root,P,Q,U,V);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
