| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13387 |
2015-02-15T16:51:31 Z |
baneling100 |
Game (IOI13_game) |
C++ |
|
0 ms |
1208 KB |
#include "game.h"
#include <stdio.h>
struct Xnode {
Xnode(int l_, int r_) {left=right=NULL, l=l_, r=r_, info=NULL;}
Xnode *left, *right;
int l, r;
long long info;
};
struct Ynode {
Ynode() {left=right=NULL, Xroot=NULL;}
Ynode *left, *right;
Xnode *Xroot;
} *Yroot;
int R, C, P, Q, U, V;
long long K;
long long gcd2(long long X, long long Y) {
long long tmp;
if(!X) {
tmp=X;
X=Y;
Y=tmp;
}
while(X!=Y && Y!=0) {
tmp=X;
X=Y;
Y=tmp%Y;
}
return X;
}
void init(int R_, int C_) {
for(R=1 ; R<R_ ; R<<=1);
for(C=1 ; C<C_ ; C<<=1);
Yroot=new Ynode();
}
long long Xcalculate(Xnode *now) {
long long value=0;
if(Q<=now->l && now->r<=V) return now->info;
else {
if(now->left!=NULL && Q<=now->left->r && now->left->l<=V) value=Xcalculate(now->left);
if(now->right!=NULL && Q<=now->right->r && now->right->l<=V) value=gcd2(value,Xcalculate(now->right));
return value;
}
}
long long Ycalculate(int l, int r, Ynode *now) {
int m=(l+r)>>1;
long long value=0;
if(P<=l && r<=U) return Xcalculate(now->Xroot);
else {
if(P<=m && now->left!=NULL) value=Ycalculate(l,m,now->left);
if(m+1<=U && now->right!=NULL) value=gcd2(value,Ycalculate(m+1,r,now->right));
return value;
}
}
void Xupdate(Xnode *now) {
int m=(now->l+now->r)>>1, x, y;
Xnode *temp;
if(now->l==Q && Q==now->r) now->info=K;
else {
if(Q<=m) {
if(now->left==NULL) now->left=new Xnode(Q,Q);
if(Q<now->left->l || now->left->r<Q) {
temp=now->left;
now->left=new Xnode(now->l,m);
if(Q<temp->l) now->left->right=temp;
else now->left->left=temp;
while(1) {
x=(now->left->r-now->left->l+1)>>1;
y=(now->left->l+now->left->r)>>1;
if(!(Q&x) && !(temp->l&x)) now->left->r=y;
else if(Q&x && temp->l&x) now->left->l=y+1;
else break;
}
}
Xupdate(now->left);
}
else {
if(now->right==NULL) now->right=new Xnode(Q,Q);
if(Q<now->right->l || now->right->r<Q) {
temp=now->right;
now->right=new Xnode(m+1,now->r);
if(Q<temp->l) now->right->right=temp;
else now->right->left=temp;
while(1) {
x=(now->right->r-now->right->l+1)>>1;
y=(now->right->l+now->right->r)>>1;
if(!(Q&x) && !(temp->l&x)) now->right->r=y;
else if(Q&x && temp->l&x) now->right->l=y+1;
else break;
}
}
Xupdate(now->right);
}
if(now->right==NULL) now->info=now->left->info;
else if(now->left==NULL) now->info=now->right->info;
else now->info=gcd2(now->left->info,now->right->info);
}
}
void Yupdate(int l, int r, Ynode *now) {
int m=(l+r)>>1;
if(l<r) {
if(P<=m) {
if(now->left==NULL) now->left=new Ynode();
Yupdate(l,m,now->left);
}
if(m+1<=P) {
if(now->right==NULL) now->right=new Ynode();
Yupdate(m+1,r,now->right);
}
if(now->right==NULL) K=Xcalculate(now->left->Xroot);
else if(now->left==NULL) K=Xcalculate(now->right->Xroot);
else K=gcd2(Xcalculate(now->left->Xroot),Xcalculate(now->right->Xroot));
}
if(now->Xroot==NULL) now->Xroot=new Xnode(0,C-1);
Xupdate(now->Xroot);
}
void update(int P_, int Q_, long long K_) {
P=P_, Q=Q_, K=K_, V=Q;
Yupdate(0,R-1,Yroot);
}
long long calculate(int P_, int Q_, int U_, int V_) {
P=P_, Q=Q_, U=U_, V=V_;
return Ycalculate(0,R-1,Yroot);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
