Submission #293981

#	Time	Username	Problem	Language	Result	Execution time	Memory
293981		AMO5	Game (IOI13_game)	C++17	10 / 100	13089 ms	12848 KiB

game

#include <bits/stdc++.h>
#include "game.h"

//modified from ainta'solution

using namespace std;

int R,C;
long long gcd(long long a, long long b){
	while(a!=b&&b!=0){
		swap(a,b);
		b=b%a;
	}
	return a;
}

struct vrt{
	vrt *cl,*cr;
	long long val;
	int k;
	vrt(int kk){
		cl=cr=NULL;
		k=kk;
		val=0ll;
	}
};

struct hor{
	hor *cl,*cr;
	vrt *cy;
	long long val;
};

hor *root;

void init(int r, int c){
	R=r; C=c;
	root = new hor();
}

void updv(int pos, long long v, vrt *node, int le, int ri){
	//cerr<<le<<"-"<<ri<<":"<<pos<<" "<<v<<"\n";
	int mid=(le+ri)>>1;
	if(node->k){
		//cerr<<node->k<<"\n";
		if(node->k==pos){
			node->val=v;
			//cerr<<"ret \n";
			return;
		}
		if(node->k<=mid)node->cl=new vrt(node->k),node->cl->val=node->val;
		else node->cr=new vrt(node->k),node->cr->val=node->val;
		node->k=0;
	}
	if(pos<=mid){
		//cerr<<"left "<<mid<<"\n";
		if(!node->cl)node->cl=new vrt(pos);
		updv(pos,v,node->cl,le,mid);
	}else{
		//cerr<<"right "<<mid<<"\n";
		if(!node->cr)node->cr=new vrt(pos);
		updv(pos,v,node->cr,mid+1,ri);
	}
	//cerr<<"okay \n";
	node->val=gcd((node->cl?node->cl->val:0),(node->cr?node->cr->val:0));
}

long long get(vrt *node, int y, int le, int ri){
	//cerr<<" get "<<le<<"-"<<ri<<" "<<y<<"\n";
	if(node==NULL)return 0;
	if(node->k){
		//cerr<<node->k<<" "<<node->val<<"\n";
		if(node->k==y)return node->val;
		return 0;
	}
	int mid=(le+ri)>>1;
	if(y<=mid)return get(node->cl,y,le,mid);
	else return get(node->cr,y,mid+1,ri);
}

void updh(int x, int y, long long v, hor *node, int le, int ri){
	//cerr<<le<<" "<<ri<<" "<<x<<" "<<y<<" "<<v<<"\n";
	if(!node->cy){
		node->cy=new vrt(y);
	}
	if(le==ri){
		updv(y,v,node->cy,1,C);
		return;
	}
	int mid=(le+ri)>>1;
	if(!node->cl)node->cl=new hor();
	if(!node->cr)node->cr=new hor();
	if(x<=mid)updh(x,y,v,node->cl,le,mid);
	else updh(x,y,v,node->cr,mid+1,ri);
	//cerr<<" okay "<<"\n";
	long long r=0ll;
	r=gcd(get(node->cl->cy,y,1,C),r);
	//cerr<<"left done\n";
	r=gcd(get(node->cr->cy,y,1,C),r);
	//cerr<<"right done\n";
	//cerr<<y<<" "<<r<<"\n";
	updv(y,r,node->cy,1,C);
}

void update(int p, int q, long long k){
	p++; q++;
	updh(p,q,k,root,1,R);
}

long long dnc(int x, int y, vrt *node, int le, int ri){
	if(node==NULL)return 0ll;
	if(node->k){
		int pos = node->k;
		if(x<=pos&&pos<=y)return node->val;
		return 0ll;
	}
	int mid=(le+ri)>>1;
	long long r = 0ll;
	if(x<=mid&&node->cl)r = gcd(r,dnc(x,y,node->cl,le,mid));
	if(y>mid&&node->cr)r = gcd(r,dnc(x,y,node->cr,mid+1,ri));
	return r;
}


long long solve(int p, int q, int u, int v, hor *node, int le, int ri){
	//cerr<<le<<"-"<<ri<<" "<<p<<" "<<q<<" "<<u<<" "<<v<<"\n";
	if(p==le&&ri==u)return dnc(q,v,node->cy,1,C);
	int mid=(le+ri)>>1;
	long long r = 0ll;
	if(p<=mid&&node->cl)r = gcd(r,solve(p,q,min(u,mid),v,node->cl,le,mid));
	if(u>mid&&node->cr)r = gcd(r,solve(max(p,mid+1),q,u,v,node->cr,mid+1,ri));
	return r;
}

long long calculate(int p, int q, int u, int v){
	p++; q++; u++; v++;
	return solve(p,q,u,v,root,1,R);
}
/*
int main(){
	//ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int r,c,q;
	cin>>r>>c>>q;
	init(r,c);
	int t,x,y,x2,y2;
	long long v;
	for(int i=0; i<q; i++){
		cin>>t;
		//cerr<<i<<" qu "<<t<<"\n";
		if(t==1){
			cin>>x>>y>>v;
			update(x,y,v);
		}else{
			cin>>x>>y>>x2>>y2;
			cout<<calculate(x,y,x2,y2)<<"\n";
		}
	}
	return 0;
}
// */ 

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