oj.uz

Submission #986357

# Submission time Handle Problem Language Result Execution time Memory
986357 2024-05-20T11:13:43 Z Pyqe Game (IOI13_game) C++17
100 / 100
 4825 ms 239136 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

int n,m,nn=0;
long long ga[12540069];
int pa[12540069][2];

long long gcd2(long long x,long long y)
{
	for(;y;)
	{
		x%=y;
		swap(x,y);
	}
	return x;
}

void sgud(int ix,int l,int r,int x,long long w)
{
	if(l>=x&&r<=x)
	{
		ga[ix]=w;
	}
	else
	{
		int ii,md=(l+r)/2,l2,r2;
		
		for(ii=0;ii<2;ii++)
		{
			l2=!ii?l:md+1;
			r2=!ii?md:r;
			if(!(l2>x||r2<x))
			{
				if(!pa[ix][ii])
				{
					nn++;
					pa[ix][ii]=nn;
				}
				sgud(pa[ix][ii],l2,r2,x,w);
			}
		}
		ga[ix]=gcd2(ga[pa[ix][0]],ga[pa[ix][1]]);
	}
}

long long sgqr(int ix,int l,int r,int lh,int rh)
{
	if(!ix||l>rh||r<lh)
	{
		return 0;
	}
	else if(l>=lh&&r<=rh)
	{
		return ga[ix];
	}
	else
	{
		long long md=(l+r)/2;
		
		return gcd2(sgqr(pa[ix][0],l,md,lh,rh),sgqr(pa[ix][1],md+1,r,lh,rh));
	}
}

struct segtreetree
{
	int l,r,sg;
	segtreetree *p[3];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		nn++;
		sg=nn;
		p[0]=0;
	}
	void blc()
	{
		if(!p[0])
		{
			int ii,md=l+(r-l)/3,md2=r-(r-l+2)/3;
			
			for(ii=0;ii<3;ii++)
			{
				p[ii]=new segtreetree;
			}
			p[0]->bd(l,md);
			p[1]->bd(md+1,md2);
			p[2]->bd(md2+1,r);
		}
	}
	long long ud(int y,int x,long long w)
	{
		if(l>y||r<y)
		{
			return sgqr(sg,0,m-1,x,x);
		}
		else if(!(l>=y&&r<=y))
		{
			int ii;
			long long k=0;
			
			blc();
			for(ii=0;ii<3;ii++)
			{
				k=gcd2(k,p[ii]->ud(y,x,w));
			}
			w=k;
		}
		sgud(sg,0,m-1,x,w);
		return w;
	}
	long long qr(int lh,int rh,int lh2,int rh2)
	{
		if(l>rh||r<lh)
		{
			return 0;
		}
		else if((l>=lh&&r<=rh)||!p[0])
		{
			return sgqr(sg,0,m-1,lh2,rh2);
		}
		else
		{
			long long ii,z=0;
			
			for(ii=0;ii<3;ii++)
			{
				z=gcd2(z,p[ii]->qr(lh,rh,lh2,rh2));
			}
			return z;
		}
	}
}
sgg;

void init(int on,int om)
{
	n=on;
	m=om;
	sgg.bd(0,n-1);
}

void update(int y,int x,long long w)
{
	sgg.ud(y,x,w);
}

long long calculate(int y,int x,int y2,int x2)
{
	return sgg.qr(y,y2,x,x2);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 506 ms 14428 KB Output is correct
5 Correct 315 ms 14108 KB Output is correct
6 Correct 341 ms 11744 KB Output is correct
7 Correct 372 ms 11360 KB Output is correct
8 Correct 275 ms 11252 KB Output is correct
9 Correct 356 ms 11580 KB Output is correct
10 Correct 339 ms 11248 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 745 ms 14868 KB Output is correct
13 Correct 1253 ms 10176 KB Output is correct
14 Correct 244 ms 7744 KB Output is correct
15 Correct 1489 ms 11024 KB Output is correct
16 Correct 157 ms 14480 KB Output is correct
17 Correct 608 ms 12328 KB Output is correct
18 Correct 918 ms 16188 KB Output is correct
19 Correct 790 ms 16540 KB Output is correct
20 Correct 725 ms 15524 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 448 ms 14564 KB Output is correct
13 Correct 300 ms 14164 KB Output is correct
14 Correct 339 ms 11784 KB Output is correct
15 Correct 376 ms 11688 KB Output is correct
16 Correct 266 ms 11088 KB Output is correct
17 Correct 372 ms 12212 KB Output is correct
18 Correct 321 ms 11036 KB Output is correct
19 Correct 747 ms 14836 KB Output is correct
20 Correct 1258 ms 10716 KB Output is correct
21 Correct 231 ms 7504 KB Output is correct
22 Correct 1479 ms 11548 KB Output is correct
23 Correct 143 ms 14508 KB Output is correct
24 Correct 601 ms 12496 KB Output is correct
25 Correct 855 ms 16012 KB Output is correct
26 Correct 773 ms 16328 KB Output is correct
27 Correct 715 ms 15580 KB Output is correct
28 Correct 481 ms 110620 KB Output is correct
29 Correct 1319 ms 121080 KB Output is correct
30 Correct 3829 ms 84264 KB Output is correct
31 Correct 3602 ms 68348 KB Output is correct
32 Correct 409 ms 12164 KB Output is correct
33 Correct 566 ms 12704 KB Output is correct
34 Correct 267 ms 114924 KB Output is correct
35 Correct 880 ms 66544 KB Output is correct
36 Correct 1748 ms 119076 KB Output is correct
37 Correct 1379 ms 119144 KB Output is correct
38 Correct 1393 ms 118908 KB Output is correct
39 Correct 1183 ms 95048 KB Output is correct
40 Correct 1 ms 2392 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 463 ms 14404 KB Output is correct
13 Correct 293 ms 14164 KB Output is correct
14 Correct 337 ms 11748 KB Output is correct
15 Correct 361 ms 11348 KB Output is correct
16 Correct 276 ms 11192 KB Output is correct
17 Correct 354 ms 11596 KB Output is correct
18 Correct 326 ms 11520 KB Output is correct
19 Correct 739 ms 15192 KB Output is correct
20 Correct 1264 ms 10028 KB Output is correct
21 Correct 244 ms 8012 KB Output is correct
22 Correct 1509 ms 11048 KB Output is correct
23 Correct 131 ms 14424 KB Output is correct
24 Correct 585 ms 12288 KB Output is correct
25 Correct 842 ms 15932 KB Output is correct
26 Correct 765 ms 16044 KB Output is correct
27 Correct 712 ms 15320 KB Output is correct
28 Correct 489 ms 110452 KB Output is correct
29 Correct 1248 ms 121136 KB Output is correct
30 Correct 3757 ms 84148 KB Output is correct
31 Correct 3530 ms 68556 KB Output is correct
32 Correct 409 ms 12112 KB Output is correct
33 Correct 549 ms 12836 KB Output is correct
34 Correct 271 ms 114816 KB Output is correct
35 Correct 869 ms 66532 KB Output is correct
36 Correct 1759 ms 119200 KB Output is correct
37 Correct 1412 ms 119056 KB Output is correct
38 Correct 1336 ms 118828 KB Output is correct
39 Correct 693 ms 217668 KB Output is correct
40 Correct 2131 ms 239136 KB Output is correct
41 Correct 4825 ms 164616 KB Output is correct
42 Correct 4517 ms 129056 KB Output is correct
43 Correct 536 ms 233688 KB Output is correct
44 Correct 503 ms 12508 KB Output is correct
45 Correct 1178 ms 94844 KB Output is correct
46 Correct 2502 ms 237820 KB Output is correct
47 Correct 2475 ms 237860 KB Output is correct
48 Correct 2344 ms 237544 KB Output is correct
49 Correct 1 ms 2396 KB Output is correct