Submission #4617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4617	2013-11-11T07:54:58 Z	cki86201	Game (IOI13_game)	C++	36 / 100	4416 ms	132416 KB

game

#include "game.h"

//36point;

const int idx = 2048;
typedef long long ll;

bool flag;
ll T[4100][4100];

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;
}

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 update(int P, int Q, long long 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;
}

long long calculate(int P, int Q, int U, int 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	Execution time	Memory	Grader output
1	Correct	0 ms	132416 KB	Output is correct
2	Correct	0 ms	132416 KB	Output is correct
3	Correct	0 ms	132416 KB	Output is correct
4	Correct	0 ms	132416 KB	Output is correct
5	Correct	0 ms	132416 KB	Output is correct
6	Correct	0 ms	132416 KB	Output is correct
7	Correct	0 ms	132416 KB	Output is correct
8	Correct	0 ms	132416 KB	Output is correct
9	Correct	0 ms	132416 KB	Output is correct
10	Correct	0 ms	132416 KB	Output is correct
11	Correct	0 ms	132416 KB	Output is correct
12	Correct	0 ms	132416 KB	Output is correct

Subtask #2

0.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	132416 KB	Output is correct
2	Correct	0 ms	132416 KB	Output is correct
3	Correct	0 ms	132416 KB	Output is correct
4	Incorrect	1360 ms	132416 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	132416 KB	Output is correct
2	Correct	0 ms	132416 KB	Output is correct
3	Correct	0 ms	132416 KB	Output is correct
4	Correct	0 ms	132416 KB	Output is correct
5	Correct	0 ms	132416 KB	Output is correct
6	Correct	0 ms	132416 KB	Output is correct
7	Correct	0 ms	132416 KB	Output is correct
8	Correct	0 ms	132416 KB	Output is correct
9	Correct	0 ms	132416 KB	Output is correct
10	Correct	0 ms	132416 KB	Output is correct
11	Correct	0 ms	132416 KB	Output is correct
12	Correct	1636 ms	132416 KB	Output is correct
13	Correct	3824 ms	132416 KB	Output is correct
14	Correct	760 ms	132416 KB	Output is correct
15	Correct	4416 ms	132416 KB	Output is correct
16	Correct	2584 ms	132416 KB	Output is correct
17	Correct	2244 ms	132416 KB	Output is correct
18	Correct	3296 ms	132416 KB	Output is correct
19	Correct	2960 ms	132416 KB	Output is correct
20	Correct	2708 ms	132416 KB	Output is correct
21	Correct	0 ms	132416 KB	Output is correct

Subtask #4

0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	132416 KB	Output is correct
2	Correct	0 ms	132416 KB	Output is correct
3	Correct	0 ms	132416 KB	Output is correct
4	Correct	0 ms	132416 KB	Output is correct
5	Correct	0 ms	132416 KB	Output is correct
6	Correct	0 ms	132416 KB	Output is correct
7	Correct	0 ms	132416 KB	Output is correct
8	Correct	0 ms	132416 KB	Output is correct
9	Correct	0 ms	132416 KB	Output is correct
10	Correct	0 ms	132416 KB	Output is correct
11	Correct	0 ms	132416 KB	Output is correct
12	Incorrect	1336 ms	132416 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	132416 KB	Output is correct
2	Correct	0 ms	132416 KB	Output is correct
3	Correct	0 ms	132416 KB	Output is correct
4	Correct	0 ms	132416 KB	Output is correct
5	Correct	0 ms	132416 KB	Output is correct
6	Correct	0 ms	132416 KB	Output is correct
7	Correct	0 ms	132416 KB	Output is correct
8	Correct	0 ms	132416 KB	Output is correct
9	Correct	0 ms	132416 KB	Output is correct
10	Correct	0 ms	132416 KB	Output is correct
11	Correct	0 ms	132416 KB	Output is correct
12	Incorrect	1336 ms	132416 KB	Output isn't correct
13	Halted	0 ms	0 KB	-