oj.uz

Submission #294015

# Submission time Handle Problem Language Result Execution time Memory
294015 2020-09-08T14:26:34 Z AMO5 Game (IOI13_game) C++17
100 / 100
 5233 ms 116088 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 0ll;
	if(node->k){
		//cerr<<node->k<<" "<<node->val<<"\n";
		if(node->k==y)return node->val;
		return 0ll;
	}
	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;
	}
	if(x<=le&&ri<=y)return node->val;	
	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.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 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 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 580 ms 12920 KB Output is correct
5 Correct 448 ms 13432 KB Output is correct
6 Correct 479 ms 11000 KB Output is correct
7 Correct 553 ms 10616 KB Output is correct
8 Correct 365 ms 8824 KB Output is correct
9 Correct 520 ms 10876 KB Output is correct
10 Correct 498 ms 10360 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
26.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 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 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 384 KB Output is correct
12 Correct 906 ms 13688 KB Output is correct
13 Correct 1566 ms 10000 KB Output is correct
14 Correct 341 ms 5880 KB Output is correct
15 Correct 1867 ms 12024 KB Output is correct
16 Correct 242 ms 15608 KB Output is correct
17 Correct 775 ms 12024 KB Output is correct
18 Correct 1490 ms 17144 KB Output is correct
19 Correct 1187 ms 17144 KB Output is correct
20 Correct 1109 ms 16664 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
17.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 0 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 384 KB Output is correct
12 Correct 561 ms 10800 KB Output is correct
13 Correct 439 ms 13432 KB Output is correct
14 Correct 483 ms 11000 KB Output is correct
15 Correct 552 ms 10648 KB Output is correct
16 Correct 360 ms 8568 KB Output is correct
17 Correct 553 ms 10688 KB Output is correct
18 Correct 496 ms 10232 KB Output is correct
19 Correct 934 ms 16632 KB Output is correct
20 Correct 1604 ms 9836 KB Output is correct
21 Correct 335 ms 5880 KB Output is correct
22 Correct 1862 ms 12196 KB Output is correct
23 Correct 233 ms 15608 KB Output is correct
24 Correct 744 ms 12280 KB Output is correct
25 Correct 1433 ms 17272 KB Output is correct
26 Correct 1197 ms 17148 KB Output is correct
27 Correct 1171 ms 16728 KB Output is correct
28 Correct 688 ms 58744 KB Output is correct
29 Correct 1584 ms 54008 KB Output is correct
30 Correct 4001 ms 49448 KB Output is correct
31 Correct 3756 ms 39176 KB Output is correct
32 Correct 636 ms 10744 KB Output is correct
33 Correct 832 ms 14252 KB Output is correct
34 Correct 322 ms 47480 KB Output is correct
35 Correct 1162 ms 31096 KB Output is correct
36 Correct 2421 ms 51584 KB Output is correct
37 Correct 1905 ms 51688 KB Output is correct
38 Correct 1798 ms 51216 KB Output is correct
39 Correct 1499 ms 42076 KB Output is correct
40 Correct 1 ms 256 KB Output is correct

Subtask #5
20.0 / 20.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 0 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 557 ms 10904 KB Output is correct
13 Correct 421 ms 13304 KB Output is correct
14 Correct 480 ms 11000 KB Output is correct
15 Correct 556 ms 10616 KB Output is correct
16 Correct 357 ms 8696 KB Output is correct
17 Correct 551 ms 10760 KB Output is correct
18 Correct 532 ms 10364 KB Output is correct
19 Correct 941 ms 16712 KB Output is correct
20 Correct 1594 ms 9748 KB Output is correct
21 Correct 341 ms 5788 KB Output is correct
22 Correct 1870 ms 12052 KB Output is correct
23 Correct 242 ms 15500 KB Output is correct
24 Correct 796 ms 12024 KB Output is correct
25 Correct 1504 ms 17016 KB Output is correct
26 Correct 1277 ms 17156 KB Output is correct
27 Correct 1168 ms 16504 KB Output is correct
28 Correct 699 ms 58432 KB Output is correct
29 Correct 1661 ms 53752 KB Output is correct
30 Correct 3871 ms 49192 KB Output is correct
31 Correct 3691 ms 39100 KB Output is correct
32 Correct 641 ms 10616 KB Output is correct
33 Correct 862 ms 14184 KB Output is correct
34 Correct 326 ms 47352 KB Output is correct
35 Correct 1253 ms 31000 KB Output is correct
36 Correct 2316 ms 51788 KB Output is correct
37 Correct 1868 ms 51672 KB Output is correct
38 Correct 1849 ms 51116 KB Output is correct
39 Correct 985 ms 116088 KB Output is correct
40 Correct 2676 ms 99724 KB Output is correct
41 Correct 5233 ms 97540 KB Output is correct
42 Correct 4905 ms 75292 KB Output is correct
43 Correct 621 ms 94608 KB Output is correct
44 Correct 874 ms 11000 KB Output is correct
45 Correct 1753 ms 42012 KB Output is correct
46 Correct 3202 ms 98668 KB Output is correct
47 Correct 3068 ms 98704 KB Output is correct
48 Correct 3123 ms 98232 KB Output is correct
49 Correct 1 ms 256 KB Output is correct