Submission #7383

#	Time	Username	Problem	Language	Result	Execution time	Memory
7383		Rhak	Game (IOI13_game)	C++98	0 / 100	0 ms	1228 KiB

game

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20