oj.uz

Submission #898095

# Submission time Handle Problem Language Result Execution time Memory
898095 2024-01-04T09:56:51 Z Muhammad_Aneeq Game (IOI13_game) C++17
63 / 100
 1086 ms 132424 KB 
#include <numeric>
#include <map>
#include <algorithm>
#include <iostream>
#include "game.h"
using namespace std;
int r,c;
map<pair<int,int>,long long>d;
struct seg1
{
	long long St[262144]={};
	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[4096]={};
	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[10]={};
seg2 St1[4096]={};
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 1 ms 348 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 6492 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 1 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 641 ms 24880 KB Output is correct
5 Correct 410 ms 24840 KB Output is correct
6 Correct 481 ms 21128 KB Output is correct
7 Correct 532 ms 23600 KB Output is correct
8 Correct 423 ms 19708 KB Output is correct
9 Correct 485 ms 20956 KB Output is correct
10 Correct 479 ms 21052 KB Output is correct
11 Correct 1 ms 4444 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 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2668 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 652 ms 66120 KB Output is correct
13 Correct 889 ms 65064 KB Output is correct
14 Correct 441 ms 58692 KB Output is correct
15 Correct 1060 ms 130204 KB Output is correct
16 Correct 162 ms 132116 KB Output is correct
17 Correct 873 ms 102256 KB Output is correct
18 Correct 1030 ms 119356 KB Output is correct
19 Correct 995 ms 119120 KB Output is correct
20 Correct 954 ms 118624 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 1 ms 600 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 604 ms 24836 KB Output is correct
13 Correct 405 ms 24956 KB Output is correct
14 Correct 466 ms 21168 KB Output is correct
15 Correct 495 ms 23732 KB Output is correct
16 Correct 450 ms 19708 KB Output is correct
17 Correct 502 ms 21112 KB Output is correct
18 Correct 456 ms 20672 KB Output is correct
19 Correct 612 ms 66436 KB Output is correct
20 Correct 905 ms 65280 KB Output is correct
21 Correct 451 ms 58448 KB Output is correct
22 Correct 1080 ms 130380 KB Output is correct
23 Correct 166 ms 132312 KB Output is correct
24 Correct 867 ms 102296 KB Output is correct
25 Correct 1057 ms 119184 KB Output is correct
26 Correct 1032 ms 118784 KB Output is correct
27 Correct 1039 ms 118636 KB Output is correct
28 Runtime error 3 ms 348 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 1 ms 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 611 ms 24732 KB Output is correct
13 Correct 403 ms 25048 KB Output is correct
14 Correct 512 ms 21312 KB Output is correct
15 Correct 495 ms 23580 KB Output is correct
16 Correct 413 ms 19832 KB Output is correct
17 Correct 563 ms 21316 KB Output is correct
18 Correct 465 ms 20568 KB Output is correct
19 Correct 656 ms 65936 KB Output is correct
20 Correct 907 ms 64716 KB Output is correct
21 Correct 482 ms 58628 KB Output is correct
22 Correct 1086 ms 130144 KB Output is correct
23 Correct 172 ms 132424 KB Output is correct
24 Correct 837 ms 102396 KB Output is correct
25 Correct 1020 ms 119684 KB Output is correct
26 Correct 981 ms 118756 KB Output is correct
27 Correct 973 ms 118892 KB Output is correct
28 Runtime error 4 ms 344 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -