oj.uz

Submission #437531

# Submission time Handle Problem Language Result Execution time Memory
437531 2021-06-26T12:42:20 Z He_Ren Game (IOI13_game) C++
100 / 100
 3264 ms 59392 KB 
#include<bits/stdc++.h>
#include"game.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

inline ll gcd(ll a,ll b){ return b? gcd(b,a%b): a;}

namespace Segment_Tree_1
{
	struct Node
	{
		Node *ls, *rs;
		int l,r;
		ll val;
		Node(void){}
		Node(int _l,int _r,ll _val): ls(0), rs(0), l(_l), r(_r), val(_val) {}
	}*hd = 0;
	inline Node* new_Node(int l,int r,ll val)
	{
		if(!hd)
		{
			static const int SIZ = 1e6;
			hd = new Node[SIZ + 1];
			for(int i=0; i<SIZ; ++i) (hd + i) -> rs = hd + i + 1;
			(hd + SIZ) -> rs = 0;
		}
		Node *res = hd; hd = hd -> rs;
		*res = Node(l,r,val);
		return res;
	}
	
	#define lson(u) u->ls,l,mid
	#define rson(u) u->rs,mid+1,r
	
	inline void push_up(Node *u){ u -> val = gcd(u -> ls -> val, u -> rs -> val);}
	
	void update(Node *&u,int l,int r,int q,ll k)
	{
//		printf("  upd: [%d, %d], %d, %lld\n",l,r,q,k);
		if(!u){ u = new_Node(q,q,k); return;}
		if(q < u -> l || u -> r < q)
		{
			int mid = (l+r)>>1;
			if(q<=mid && u -> r <= mid){ update(u, l, mid, q, k); return;}
			if(mid<q && mid < u -> l){ update(u, mid+1, r, q, k); return;}
//			printf("  new node [%d, %d]\n",l,r);
			Node *v = u; u = new_Node(l,r,u -> val);
			if(q<=mid) update(u -> ls,q,q,q,k), u -> rs = v;
			else update(u -> rs,q,q,q,k), u -> ls = v;
			push_up(u);
		}
		else
		{
			l = u -> l; r = u -> r;
			if(l == r){ u -> val = k; return;}
			int mid = (l+r)>>1;
			if(q<=mid) update(lson(u),q,k);
			else update(rson(u),q,k);
			push_up(u);
		}
	}
	ll query(Node *u,int ql,int qr)
	{
		if(!u) return 0;
//		printf("  qry: u = [%d, %d], q = [%d, %d]\n",u -> l,u -> r,ql,qr);
		if(!u || qr < u -> l || u -> r < ql) return 0;
		if(ql <= u -> l && u -> r <= qr) return u -> val;
		return gcd(query(u -> ls, ql,qr), query(u -> rs, ql,qr));
	}
}

namespace Segment_Tree_2
{
	using namespace Segment_Tree_1;
	typedef Segment_Tree_1::Node Segt;
	struct Node
	{
		Node *ls,*rs;
		Segt *val;
		Node(void){}
		Node(Segt *_val): ls(0), rs(0), val(_val) {}
	}*rt = 0, *hd = 0;
	inline Node* new_Node(void)
	{
		if(!hd)
		{
			static const int SIZ = 1e6;
			hd = new Node[SIZ + 1];
			for(int i=0; i<SIZ; ++i) (hd + i) -> rs = hd + i + 1;
			(hd + SIZ) -> rs = 0;
		}
		Node *res = hd; hd = hd -> rs;
		*res = Node(0);
		return res;
	}
	
	int n,m;
	void update(Node *&u,int l,int r,int qx,int qy,ll k)
	{
		if(!u) u = new_Node();
//		printf("upd: [%d, %d], qx = %d, qy = %d, k = %lld\n",l,r,qx,qy,k);
		if(l == r){ update(u -> val, 1, m, qy, k); return;}
		int mid = (l+r)>>1;
		if(qx<=mid) update(lson(u), qx, qy, k);
		else update(rson(u), qx, qy, k);
		ll res1 = u -> ls? query(u -> ls -> val, qy, qy): 0;
		ll res2 = u -> rs? query(u -> rs -> val, qy, qy): 0;
//		printf("[%d, %d]: %d <= gcd(%lld, %lld) = %lld\n",l,r,qy,res1,res2,gcd(res1,res2));
		update(u -> val, 1, m, qy, gcd(res1, res2));
	}
	inline void update(int qx,int qy,ll k){ update(rt,1,n,qx,qy,k);}
	ll query(Node *u,int l,int r,int xl,int xr,int yl,int yr)
	{
		if(!u) return 0;
//		printf("qry: [%d, %d]\n",l,r);
		if(xl <= l && r <= xr) return query(u -> val, yl,yr);
		int mid = (l+r)>>1;
		if(xl<=mid && mid<xr) return gcd(query(lson(u),xl,xr,yl,yr), query(rson(u),xl,xr,yl,yr));
		return xl<=mid? query(lson(u),xl,xr,yl,yr): query(rson(u),xl,xr,yl,yr);
	}
	inline ll query(int xl,int xr,int yl,int yr){ return query(rt,1,n,xl,xr,yl,yr);}
}

void init(int n,int m)
{
	Segment_Tree_2::n = n; Segment_Tree_2::m = m;
}

void update(int x,int y,ll k)
{
	++x; ++y;
//	printf("\nupdate: %d %d %lld\n",x,y,k);
	Segment_Tree_2::update(x,y,k);
}

ll calculate(int xl,int yl,int xr,int yr)
{
	++xl; ++yl; ++xr; ++yr;
//	printf("\nquery: %d %d %d %d\n",xl,xr,yl,yr);
	return Segment_Tree_2::query(xl,xr,yl,yr);
}

//#define He_Ren

#ifdef He_Ren

int main(void)
{
	int _n,_m,Q;
	scanf("%d%d%d",&_n,&_m,&Q);
	init(_n, _m);
	while(Q--)
	{
		int oper;
		scanf("%d",&oper);
		if(oper == 1)
		{
			int x,y;
			ll k;
			scanf("%d%d%lld",&x,&y,&k);
			update(x,y,k);
		}
		else
		{
			int xl,yl,xr,yr;
			scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
			printf("%lld\n",calculate(xl,yl,xr,yr));
		}
	}
	return 0;
}

#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 54988 KB Output is correct
2 Correct 24 ms 55048 KB Output is correct
3 Correct 26 ms 55000 KB Output is correct
4 Correct 24 ms 54988 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 23 ms 54980 KB Output is correct
7 Correct 23 ms 55124 KB Output is correct
8 Correct 24 ms 55092 KB Output is correct
9 Correct 24 ms 54988 KB Output is correct
10 Correct 24 ms 55008 KB Output is correct
11 Correct 22 ms 54988 KB Output is correct
12 Correct 23 ms 55104 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55096 KB Output is correct
2 Correct 27 ms 55012 KB Output is correct
3 Correct 26 ms 55032 KB Output is correct
4 Correct 575 ms 59116 KB Output is correct
5 Correct 418 ms 59380 KB Output is correct
6 Correct 478 ms 56184 KB Output is correct
7 Correct 531 ms 55908 KB Output is correct
8 Correct 350 ms 56696 KB Output is correct
9 Correct 500 ms 55944 KB Output is correct
10 Correct 482 ms 55520 KB Output is correct
11 Correct 24 ms 54988 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 55036 KB Output is correct
2 Correct 22 ms 54992 KB Output is correct
3 Correct 24 ms 55048 KB Output is correct
4 Correct 24 ms 54988 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 23 ms 54988 KB Output is correct
7 Correct 25 ms 55040 KB Output is correct
8 Correct 24 ms 54992 KB Output is correct
9 Correct 23 ms 55000 KB Output is correct
10 Correct 24 ms 55052 KB Output is correct
11 Correct 24 ms 55056 KB Output is correct
12 Correct 1010 ms 59068 KB Output is correct
13 Correct 1655 ms 55780 KB Output is correct
14 Correct 260 ms 55748 KB Output is correct
15 Correct 1857 ms 55920 KB Output is correct
16 Correct 231 ms 55748 KB Output is correct
17 Correct 686 ms 56420 KB Output is correct
18 Correct 1221 ms 56136 KB Output is correct
19 Correct 1046 ms 56388 KB Output is correct
20 Correct 920 ms 55844 KB Output is correct
21 Correct 22 ms 54988 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 54972 KB Output is correct
2 Correct 23 ms 55024 KB Output is correct
3 Correct 24 ms 55088 KB Output is correct
4 Correct 26 ms 55028 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 24 ms 55068 KB Output is correct
7 Correct 25 ms 55012 KB Output is correct
8 Correct 23 ms 55020 KB Output is correct
9 Correct 23 ms 54988 KB Output is correct
10 Correct 23 ms 55036 KB Output is correct
11 Correct 23 ms 54980 KB Output is correct
12 Correct 615 ms 59056 KB Output is correct
13 Correct 415 ms 59392 KB Output is correct
14 Correct 482 ms 56292 KB Output is correct
15 Correct 542 ms 55972 KB Output is correct
16 Correct 354 ms 56664 KB Output is correct
17 Correct 507 ms 55984 KB Output is correct
18 Correct 483 ms 55600 KB Output is correct
19 Correct 924 ms 59224 KB Output is correct
20 Correct 1583 ms 55752 KB Output is correct
21 Correct 255 ms 55588 KB Output is correct
22 Correct 1817 ms 56080 KB Output is correct
23 Correct 242 ms 55732 KB Output is correct
24 Correct 684 ms 56384 KB Output is correct
25 Correct 1302 ms 56176 KB Output is correct
26 Correct 975 ms 56332 KB Output is correct
27 Correct 913 ms 55692 KB Output is correct
28 Correct 407 ms 55608 KB Output is correct
29 Correct 1299 ms 58840 KB Output is correct
30 Correct 2676 ms 55804 KB Output is correct
31 Correct 2487 ms 55832 KB Output is correct
32 Correct 344 ms 55592 KB Output is correct
33 Correct 443 ms 55596 KB Output is correct
34 Correct 271 ms 55784 KB Output is correct
35 Correct 864 ms 56368 KB Output is correct
36 Correct 1845 ms 56232 KB Output is correct
37 Correct 1332 ms 56348 KB Output is correct
38 Correct 1243 ms 55680 KB Output is correct
39 Correct 1141 ms 56444 KB Output is correct
40 Correct 25 ms 54988 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 55020 KB Output is correct
2 Correct 25 ms 54988 KB Output is correct
3 Correct 26 ms 54988 KB Output is correct
4 Correct 28 ms 54980 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 23 ms 55076 KB Output is correct
7 Correct 23 ms 54988 KB Output is correct
8 Correct 24 ms 55052 KB Output is correct
9 Correct 31 ms 55100 KB Output is correct
10 Correct 23 ms 54988 KB Output is correct
11 Correct 27 ms 54988 KB Output is correct
12 Correct 599 ms 59048 KB Output is correct
13 Correct 412 ms 59344 KB Output is correct
14 Correct 481 ms 56068 KB Output is correct
15 Correct 520 ms 55832 KB Output is correct
16 Correct 395 ms 56720 KB Output is correct
17 Correct 531 ms 56008 KB Output is correct
18 Correct 467 ms 55644 KB Output is correct
19 Correct 918 ms 59196 KB Output is correct
20 Correct 1674 ms 55956 KB Output is correct
21 Correct 260 ms 55584 KB Output is correct
22 Correct 1822 ms 55788 KB Output is correct
23 Correct 229 ms 55748 KB Output is correct
24 Correct 680 ms 56296 KB Output is correct
25 Correct 1224 ms 56176 KB Output is correct
26 Correct 1020 ms 56192 KB Output is correct
27 Correct 930 ms 55868 KB Output is correct
28 Correct 386 ms 55620 KB Output is correct
29 Correct 1259 ms 58708 KB Output is correct
30 Correct 2646 ms 55560 KB Output is correct
31 Correct 2407 ms 55732 KB Output is correct
32 Correct 355 ms 55620 KB Output is correct
33 Correct 459 ms 55592 KB Output is correct
34 Correct 286 ms 55784 KB Output is correct
35 Correct 848 ms 56388 KB Output is correct
36 Correct 1919 ms 56216 KB Output is correct
37 Correct 1368 ms 56240 KB Output is correct
38 Correct 1328 ms 55912 KB Output is correct
39 Correct 496 ms 55568 KB Output is correct
40 Correct 1952 ms 57764 KB Output is correct
41 Correct 3264 ms 55484 KB Output is correct
42 Correct 3116 ms 55684 KB Output is correct
43 Correct 473 ms 55716 KB Output is correct
44 Correct 416 ms 55656 KB Output is correct
45 Correct 1114 ms 56260 KB Output is correct
46 Correct 2654 ms 56096 KB Output is correct
47 Correct 2500 ms 56004 KB Output is correct
48 Correct 2455 ms 55640 KB Output is correct
49 Correct 22 ms 54988 KB Output is correct