oj.uz

Submission #293972

# Submission time Handle Problem Language Result Execution time Memory
293972 2020-09-08T14:12:18 Z AMO5 Game (IOI13_game) C++17
10 / 100
 13000 ms 11952 KB 
#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>ri||le>u)return 0ll;
	if(p<=le&&ri<=u)return dnc(q,v,node->cy,1,C);
	int mid=(le+ri)>>1;
	long long r = 0ll;
	if(node->cl)r = gcd(r,solve(p,q,u,v,node->cl,le,mid));
	if(node->cr)r = gcd(r,solve(p,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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Execution timed out 13070 ms 9128 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13068 ms 11952 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13012 ms 8260 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 416 KB Output is correct
12 Execution timed out 13067 ms 6116 KB Time limit exceeded
13 Halted 0 ms 0 KB -