Submission #4618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4618	2013-11-11T08:03:46 Z	cki86201	Game (IOI13_game)	C++	63 / 100	4416 ms	152728 KB

game

#include "game.h"

//63point;

const int idx = 2048;
const int idx2 = 131072;
typedef long long ll;

int flag;
ll T[4100][4100];
ll T2[10][260000];

ll gc(ll x,ll y){
	ll tmp=-1;
	while(x!=tmp&&y)tmp=x,x=y,y=tmp%y;
	return x;
}

void init(int R, int C){
	if(R<=2000&&C<=2000)flag=1;
	else if(R<=10&&C<=100000)flag=2;
	else flag=3;
}

void upd1(int x,int y,ll K)
{
	int y1=y+idx;
	T[x][y1]=gc(T[x<<1][y1],T[x<<1|1][y1]);
	y1>>=1;
	while(y1){
		T[x][y1]=gc(T[x][y1<<1],T[x][y1<<1|1]);
		y1>>=1;
	}
}

void update2(int x,int y,ll item)
{
	y+=idx2;
	T2[x][y]=item;
	y>>=1;
	while(y){
		T2[x][y]=gc(T2[x][y<<1],T2[x][y<<1|1]);
		y>>=1;
	}
}

void update(int P, int Q, long long K){
	if(flag==3)return;
	if(flag==2)update2(P,Q,K);
	int p=P+idx,q=Q+idx;
	T[p][q]=K;q>>=1;
	while(q){T[p][q]=gc(T[p][q<<1],T[p][q<<1|1]);q>>=1;}
	p>>=1;
	while(p){
		upd1(p,Q,K);
		p>>=1;
	}
}

ll cal1(int p,int s,int d)
{
	int s1=s+idx,d1=d+idx;
	ll ret=0;
	while(s1<=d1){
		ret=gc(ret,T[p][s1]);
		ret=gc(ret,T[p][d1]);
		s1=(s1+1)>>1;
		d1=(d1-1)>>1;
	}
	return ret;
}

ll read2(int t,int x,int y)
{
	ll ret=0;
	x+=idx2,y+=idx2;
	while(x<=y){
		ret=gc(ret,T2[t][x]);
		ret=gc(ret,T2[t][y]);
		x=(x+1)>>1;
		y=(y-1)>>1;
	}
	return ret;
}

ll calculate2(int P, int Q, int U, int V){
	ll ret=0;
	for(int i=P;i<=U;i++)ret=gc(ret,read2(i,Q,V));
	return ret;
}

ll calculate(int P, int Q, int U, int V){
	if(flag==3)return -1;
	if(flag==2)return calculate2(P,Q,U,V);
	int p=P+idx,q=U+idx;
	ll ret=0;
	while(p<=q){
		ret=gc(ret,cal1(p,Q,V));
		ret=gc(ret,cal1(q,Q,V));
		p=(p+1)>>1;
		q=(q-1)>>1;
	}
	return ret;
}

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	152728 KB	Output is correct
2	Correct	152728 KB	Output is correct
3	Correct	152728 KB	Output is correct
4	Correct	152728 KB	Output is correct
5	Correct	152728 KB	Output is correct
6	Correct	152728 KB	Output is correct
7	Correct	152728 KB	Output is correct
8	Correct	152728 KB	Output is correct
9	Correct	152728 KB	Output is correct
10	Correct	152728 KB	Output is correct
11	Correct	152728 KB	Output is correct
12	Correct	152728 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	152728 KB	Output is correct
2	Correct	0 ms	152728 KB	Output is correct
3	Correct	0 ms	152728 KB	Output is correct
4	Correct	1220 ms	152728 KB	Output is correct
5	Correct	764 ms	152728 KB	Output is correct
6	Correct	1296 ms	152728 KB	Output is correct
7	Correct	1392 ms	152728 KB	Output is correct
8	Correct	868 ms	152728 KB	Output is correct
9	Correct	1412 ms	152728 KB	Output is correct
10	Correct	1116 ms	152728 KB	Output is correct
11	Correct	0 ms	152728 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	152728 KB	Output is correct
2	Correct	0 ms	152728 KB	Output is correct
3	Correct	0 ms	152728 KB	Output is correct
4	Correct	0 ms	152728 KB	Output is correct
5	Correct	0 ms	152728 KB	Output is correct
6	Correct	0 ms	152728 KB	Output is correct
7	Correct	0 ms	152728 KB	Output is correct
8	Correct	0 ms	152728 KB	Output is correct
9	Correct	0 ms	152728 KB	Output is correct
10	Correct	0 ms	152728 KB	Output is correct
11	Correct	0 ms	152728 KB	Output is correct
12	Correct	1688 ms	152728 KB	Output is correct
13	Correct	3772 ms	152728 KB	Output is correct
14	Correct	764 ms	152728 KB	Output is correct
15	Correct	4416 ms	152728 KB	Output is correct
16	Correct	2596 ms	152728 KB	Output is correct
17	Correct	2216 ms	152728 KB	Output is correct
18	Correct	3300 ms	152728 KB	Output is correct
19	Correct	3000 ms	152728 KB	Output is correct
20	Correct	2792 ms	152728 KB	Output is correct
21	Correct	0 ms	152728 KB	Output is correct

Subtask #4
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	152728 KB	Output is correct
2	Correct	0 ms	152728 KB	Output is correct
3	Correct	0 ms	152728 KB	Output is correct
4	Correct	0 ms	152728 KB	Output is correct
5	Correct	0 ms	152728 KB	Output is correct
6	Correct	0 ms	152728 KB	Output is correct
7	Correct	0 ms	152728 KB	Output is correct
8	Correct	0 ms	152728 KB	Output is correct
9	Correct	0 ms	152728 KB	Output is correct
10	Correct	0 ms	152728 KB	Output is correct
11	Correct	0 ms	152728 KB	Output is correct
12	Correct	1228 ms	152728 KB	Output is correct
13	Correct	760 ms	152728 KB	Output is correct
14	Correct	1288 ms	152728 KB	Output is correct
15	Correct	1392 ms	152728 KB	Output is correct
16	Correct	864 ms	152728 KB	Output is correct
17	Correct	1392 ms	152728 KB	Output is correct
18	Correct	1112 ms	152728 KB	Output is correct
19	Correct	1648 ms	152728 KB	Output is correct
20	Correct	3772 ms	152728 KB	Output is correct
21	Correct	764 ms	152728 KB	Output is correct
22	Correct	4412 ms	152728 KB	Output is correct
23	Correct	2640 ms	152728 KB	Output is correct
24	Correct	2300 ms	152728 KB	Output is correct
25	Correct	3388 ms	152728 KB	Output is correct
26	Correct	3144 ms	152728 KB	Output is correct
27	Correct	2880 ms	152728 KB	Output is correct
28	Incorrect	208 ms	152728 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	152728 KB	Output is correct
2	Correct	0 ms	152728 KB	Output is correct
3	Correct	0 ms	152728 KB	Output is correct
4	Correct	0 ms	152728 KB	Output is correct
5	Correct	0 ms	152728 KB	Output is correct
6	Correct	0 ms	152728 KB	Output is correct
7	Correct	0 ms	152728 KB	Output is correct
8	Correct	0 ms	152728 KB	Output is correct
9	Correct	0 ms	152728 KB	Output is correct
10	Correct	0 ms	152728 KB	Output is correct
11	Correct	0 ms	152728 KB	Output is correct
12	Correct	1240 ms	152728 KB	Output is correct
13	Correct	744 ms	152728 KB	Output is correct
14	Correct	1312 ms	152728 KB	Output is correct
15	Correct	1404 ms	152728 KB	Output is correct
16	Correct	872 ms	152728 KB	Output is correct
17	Correct	1376 ms	152728 KB	Output is correct
18	Correct	1120 ms	152728 KB	Output is correct
19	Correct	1636 ms	152728 KB	Output is correct
20	Correct	3748 ms	152728 KB	Output is correct
21	Correct	764 ms	152728 KB	Output is correct
22	Correct	4376 ms	152728 KB	Output is correct
23	Correct	2616 ms	152728 KB	Output is correct
24	Correct	2284 ms	152728 KB	Output is correct
25	Correct	3348 ms	152728 KB	Output is correct
26	Correct	3020 ms	152728 KB	Output is correct
27	Correct	2760 ms	152728 KB	Output is correct
28	Incorrect	204 ms	152728 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Submission #4618

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0