| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 7383 |
2014-08-04T18:53:43 Z |
Rhak |
Game (IOI13_game) |
C++ |
|
0 ms |
1228 KB |
#include "game.h"
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long gcd(long long x,long long y){return (y==0)? x:gcd(y,x%y);}
struct RB_Tree;
struct node{
node(){}
node(int key,long long value):key(key),red(1),value(value){link[0]=link[1]=0;root=NULL;gcd=value;}
node(int key,long long value,RB_Tree* root):key(key),red(1),value(value),root(root){link[0]=link[1]=0;gcd=value;}
int red, key;
long long value, gcd;
node *link[2];
RB_Tree *root;
};
struct RB_Tree
{
node* root;
RB_Tree(){ root = NULL; }
bool is_red(node *x){ return x && x->red==1;}
long long getGcd(node *x){ return x?x->gcd:0;}
void setGcd(node* x){ x->gcd = gcd( gcd( getGcd(x->link[0]) , getGcd(x->link[1]) ), x->value); }
node *rotate1(node *root,int dir)
{
node *save = root->link[!dir];
save->gcd = root->gcd; save->root = root->root;
setGcd(root);
//root->root = merge(root->link[dir], save->link[dir]);
root->link[!dir] = save->link[dir];
save->link[dir] = root;
root->red = 1;
save->red = 0;
return save;
}
node *rotate2(node *root,int dir)
{
root->link[!dir] = rotate1(root->link[!dir],!dir);
return rotate1(root,dir);
}
bool insert(int key, long long value){
bool res = true;
root = rb_insert(root, key, value, &res);
root->red = 0;
return res;
}
node *rb_insert(node *root,int key,long long value,bool* res)
{
if(!root) root = new node(key,value), *res = true;
else if(root->key != key){
int dir = root->key < key;
root->link[dir] = rb_insert(root->link[dir],key,value,res);
setGcd(root);
if(is_red(root->link[dir])){
if(is_red(root->link[!dir])){
root->red = 1;
root->link[0]->red = root->link[1]->red = 0;
}
else{
if(is_red(root->link[dir]->link[dir])) root = rotate1(root,!dir);
else if(is_red(root->link[dir]->link[!dir])) root = rotate2(root,!dir);
}
}
}
else *res = false;
return root;
}
bool erase(int key){
bool res = true;
root = rb_erase(root, key, &res);
return res;
}
node *rb_erase(node* root, int key, bool *res)
{
if(!root){
*res = false;
return NULL;
}
if(!is_red(root->link[0])&& !is_red(root->link[1]))root->red = 1;
node head = node(0,0);
node *q, *p, *g;
node *f = 0;
int dir = 1;
q = &head;
g = p = 0;
q->link[1] = root;
while(q->link[dir]){
int last = dir;
g = p, p = q;
q = q->link[dir];
dir = q->key < key;
if(!f && q->key == key )f=q;
if(is_red(q) || is_red(q->link[dir]))continue;
if(is_red(q->link[!dir]))p = p->link[last] = rotate1(q,dir);
else if(!is_red(q->link[!dir])){
node *s = p->link[!last];
if(!s)continue;
if(!is_red(s->link[!last]) && !is_red(s->link[last]))p->red = 0, s->red = 1, q->red = 1;
else{
int dir2 = g->link[1] == p;
if(is_red(s->link[last]))g->link[dir2] = rotate2(p,last);
else if(is_red(s->link[!last]))g->link[dir2] = rotate1(p,last);
q->red = g->link[dir2]->red = 1;
g->link[dir2]->link[0]->red = 0;
g->link[dir2]->link[1]->red = 0;
}
}
}
if(f){
f->key = q->key;
p->link[p->link[1]==q] = q->link[!q->link[0]];
free(q);
q = &head; dir = 1;
while(q != p){
q = q->link[dir]; setGcd(q);
dir = q->key < p->key;
}
*res = true;
}
else *res = false;
root = head.link[1];
if(root)root->red = 0;
return root;
}
void clear(){ return clear(root); }
void clear(node* root){ if(!root) clear(root->link[0]), clear(root->link[1]); free(root); }
long long findGcd(int st, int en)
{
if(!root) return 0;
long long ans = 0;
node *l = root, *r = root;
while(r == l){
if(!r && !l) return ans;
int dir1 = l->key < st, dir2 = r->key < en;
if(st <= l->key && l->key <= en) ans = l->value;
l = l->link[dir1], r = r->link[dir2];
}
while( l ){
int dir = l->key < st;
if(dir == 0) ans = gcd(ans, gcd(l->value,getGcd(l->link[1])) );
l = l->link[dir];
}
while( r ){
int dir = r->key > en;
if(dir == 0) ans = gcd(ans, gcd(r->value,getGcd(r->link[0]) ));
r = r->link[dir];
}
return ans;
}
}Tree[2005];
void init(int R, int C)
{
}
void update(int P,int Q,long long K)
{
if(!Tree[P].insert(Q,K)){
Tree[P].erase(Q);
Tree[P].insert(Q,K);
}
}
long long calculate(int P,int Q,int U, int V)
{
long long ans = 0;
for(int i = P; i <= U; i++){
ans = gcd(ans,Tree[i].findGcd(Q,V));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1228 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1228 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1228 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1228 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1228 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
