oj.uz

Submission #898075

# Submission time Handle Problem Language Result Execution time Memory
898075 2024-01-04T09:41:23 Z Muhammad_Aneeq Game (IOI13_game) C++17
63 / 100
 1081 ms 200396 KB 
#include <numeric>
#include <map>
#include <algorithm>
#include <iostream>
#include "game.h"
using namespace std;
int r,c;
int const N=1e5,N2=2000+10;;
map<pair<int,int>,long long>d;
struct seg1
{
	long long St[4*N]={};
	void update(int i,int r,int st,int en,long long val)
	{
		if (st==en)
		{
			St[i]=val;
			return;
		}
		int mid=(st+en)/2;
		if (r<=mid)
			update(i*2,r,st,mid,val);
		else
			update(i*2+1,r,mid+1,en,val);
		St[i]=gcd(St[i*2],St[i*2+1]);
	}
	long long get(int i,int st,int en,int l,int r)
	{
		if (st>=l&&en<=r)
			return St[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
	}
};
struct seg2
{
	long long St[3*N2]={};
	void update(int i,int l,int r,int st,int en,long long val)
	{
		if (st>r||en<l)
			return;
		if (st>=l&&en<=r)
		{
			St[i]=val;return;
		}
		int mid=(st+en)/2;
		update(i*2,l,r,st,mid,val);update(i*2+1,l,r,mid+1,en,val);
		St[i]=gcd(St[i*2],St[i*2+1]);
	}
	long long get(int i,int st,int en,int l,int r)
	{
		if (st>=l&&en<=r)
			return St[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
	}
};
seg1 St[50]={};
seg2 St1[3*N2]={};
void update(int i,int l,int r,int k,int j,int st,int en,long long val)
{
	if (st>r||en<l)
		return ;
	if (st>=l&&en<=r)
	{
		St1[i].update(1,k,k,0,c-1,val);
		return;
	}
	int mid=(st+en)/2;
	update(i*2,l,r,k,j,st,mid,val);update(i*2+1,l,r,k,j,mid+1,en,val);
	long long f=gcd(St1[i*2].get(1,0,c-1,k,k),St1[i*2+1].get(1,0,c-1,k,k));
	St1[i].update(1,k,k,0,c-1,f);
}
long long get(int i,int l,int r,int k,int j,int st,int en)
{
	if (st>=l&&en<=r)
		return St1[i].get(1,0,c-1,k,j);
	if (st>r||en<l)
		return 0;
	int mid=(st+en)/2;
	return gcd(get(i*2,l,r,k,j,st,mid),get(i*2+1,l,r,k,j,mid+1,en));
}
void init(int R, int C)
{
	r=R;
	c=C;
}
void update(int P, int Q, long long K)
{
	if (r<=10)
		St[P].update(1,Q,0,c-1,K);
	else
		update(1,P,P,Q,Q,0,r-1,K);
}
long long calculate(int P, int Q, int U, int V)
{
	if (r<=10)
	{
		long long ans=0;
		for (int i=P;i<=U;i++)
		{
			long long z=St[i].get(1,0,c-1,Q,V);
			ans=gcd(ans,z);
		}
		return ans;
	}
	long long ans=get(1,P,U,Q,V,0,r-1);
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 606 ms 26584 KB Output is correct
5 Correct 402 ms 26888 KB Output is correct
6 Correct 481 ms 21272 KB Output is correct
7 Correct 463 ms 33872 KB Output is correct
8 Correct 404 ms 19680 KB Output is correct
9 Correct 524 ms 20948 KB Output is correct
10 Correct 447 ms 20664 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 613 ms 92360 KB Output is correct
13 Correct 919 ms 93528 KB Output is correct
14 Correct 466 ms 72788 KB Output is correct
15 Correct 1016 ms 194360 KB Output is correct
16 Correct 169 ms 200396 KB Output is correct
17 Correct 828 ms 115220 KB Output is correct
18 Correct 1024 ms 136740 KB Output is correct
19 Correct 1053 ms 135504 KB Output is correct
20 Correct 1022 ms 134716 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 606 ms 26556 KB Output is correct
13 Correct 398 ms 27044 KB Output is correct
14 Correct 455 ms 21400 KB Output is correct
15 Correct 481 ms 34056 KB Output is correct
16 Correct 402 ms 19928 KB Output is correct
17 Correct 488 ms 21176 KB Output is correct
18 Correct 424 ms 20468 KB Output is correct
19 Correct 611 ms 92456 KB Output is correct
20 Correct 862 ms 93468 KB Output is correct
21 Correct 421 ms 72884 KB Output is correct
22 Correct 1033 ms 194280 KB Output is correct
23 Correct 178 ms 200204 KB Output is correct
24 Correct 859 ms 115388 KB Output is correct
25 Correct 1056 ms 136620 KB Output is correct
26 Correct 1008 ms 135312 KB Output is correct
27 Correct 968 ms 134736 KB Output is correct
28 Runtime error 9 ms 524 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 12712 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 572 ms 26700 KB Output is correct
13 Correct 398 ms 26932 KB Output is correct
14 Correct 493 ms 21380 KB Output is correct
15 Correct 477 ms 33876 KB Output is correct
16 Correct 389 ms 19740 KB Output is correct
17 Correct 488 ms 21120 KB Output is correct
18 Correct 445 ms 20672 KB Output is correct
19 Correct 605 ms 92264 KB Output is correct
20 Correct 897 ms 93436 KB Output is correct
21 Correct 448 ms 72908 KB Output is correct
22 Correct 1022 ms 194060 KB Output is correct
23 Correct 188 ms 200300 KB Output is correct
24 Correct 827 ms 115296 KB Output is correct
25 Correct 1081 ms 136956 KB Output is correct
26 Correct 1004 ms 135508 KB Output is correct
27 Correct 960 ms 134860 KB Output is correct
28 Runtime error 9 ms 348 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -