Submission #123805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
123805	2019-07-02T07:13:02 Z	Mahdi_Jfri	Game (IOI13_game)	C++14	100 / 100	11260 ms	28188 KB

game

//#include "grader.h"
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 22e3 + 20;
const int maxb = 17;
const int sq = 150;

int sz;

int x[maxn] , y[maxn] , tmp[maxn] , seg[maxb][maxn] , where[maxb][maxn];
ll g[maxb][maxn * 4] , val[maxn];

vector<int> cmpx;

map<pair<int , int> , int> MP;

bool cmpy(int a , int b)
{
	return y[a] < y[b];
}

void build(int s = 0 , int e = cmpx.size() , int h = 0)
{
	if(e - s < 2)
	{
		seg[h][s] = tmp[s];
		where[h][tmp[s]] = s;
		return;
	}

	int m = (s + e) / 2;
	build(s , m , h + 1);
	build(m , e , h + 1);

	merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s , cmpy);
	for(int i = s; i < e; i++)
		where[h][seg[h][i]] = i;
}

void buildgcd(int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(e - s < 2)
	{
		g[h][v] = val[seg[h][s]];
		return;
	}

	int m = (s + e) / 2;
	buildgcd(h , s , m , 2 * v);
	buildgcd(h , m , e , 2 * v + 1);

	g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}

void updategcd(int p , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(e - s < 2)
	{
		g[h][v] = val[seg[h][s]];
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		updategcd(p , h , s , m , 2 * v);
	else
		updategcd(p , h , m , e , 2 * v + 1);

	g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}

ll getGcd(int l , int r , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(l <= s && e <= r)
		return g[h][v];
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;
	return __gcd(getGcd(l , r , h , s , m , 2 * v) , getGcd(l , r , h , m , e , 2 * v + 1));
}

ll get(int l , int r , int l2 , int r2 , int s = 0 , int e = cmpx.size() , int h = 0)
{
	if(l <= s && e <= r)
	{
		y[maxn - 1] = l2; l2 = lower_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
		y[maxn - 1] = r2; r2 = upper_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
		return getGcd(l2 , r2 , h);
	}
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;

	return __gcd(get(l , r , l2 , r2 , s , m , h + 1) , get(l , r , l2 , r2 , m , e , h + 1));
}

void rebuild()
{
	memset(where , -1 , sizeof where);
	cmpx.clear();
	for(int i = 0; i < sz; i++)
		cmpx.pb(x[i]);

	sort(cmpx.begin() , cmpx.end());

	map<int , int> mp;
	for(int i = 0; i < sz; i++)
	{
		int p = lower_bound(cmpx.begin() , cmpx.end() , x[i]) - cmpx.begin();
		p += mp[x[i]];
		mp[x[i]]++;

		tmp[p] = i;
	}

	build();
	for(int i = 0; i < maxb; i++)
		buildgcd(i);
}

void init(int R, int C)
{
	memset(where , -1 , sizeof where);
	R = R , C = C;
}

void update(int P, int Q, long long K)
{
	if(MP.count({P , Q}))
	{
		int ind = MP[make_pair(P , Q)];
		val[ind] = K;

		for(int i = 0; i < maxb; i++)
			if(where[i][ind] != -1)
				updategcd(where[i][ind] , i);
	}
	else
	{
		x[sz] = P , y[sz] = Q , val[sz] = K;
		MP[make_pair(P , Q)] = sz;
		sz++;
		if(sz % sq == 0)
			rebuild();
	}
}

long long calculate(int l1, int l2, int r1, int r2)
{
	ll res = 0;
	for(int i = sz / sq * sq; i < sz; i++)
		if(l1 <= x[i] && x[i] <= r1 && l2 <= y[i] && y[i] <= r2)
			res = __gcd(res , val[i]);

	int l = lower_bound(cmpx.begin() , cmpx.end() , l1) - cmpx.begin();
	int r = upper_bound(cmpx.begin() , cmpx.end() , r1) - cmpx.begin();

	return __gcd(res , get(l , r , l2 , r2));
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	3 ms	1784 KB	Output is correct
3	Correct	3 ms	1784 KB	Output is correct
4	Correct	2478 ms	14656 KB	Output is correct
5	Correct	1403 ms	13816 KB	Output is correct
6	Correct	2528 ms	10376 KB	Output is correct
7	Correct	2896 ms	10076 KB	Output is correct
8	Correct	1306 ms	8056 KB	Output is correct
9	Correct	2775 ms	10360 KB	Output is correct
10	Correct	3474 ms	9928 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1788 KB	Output is correct
2	Correct	3 ms	1784 KB	Output is correct
3	Correct	3 ms	1784 KB	Output is correct
4	Correct	3 ms	1784 KB	Output is correct
5	Correct	3 ms	1784 KB	Output is correct
6	Correct	3 ms	1784 KB	Output is correct
7	Correct	4 ms	1784 KB	Output is correct
8	Correct	4 ms	1784 KB	Output is correct
9	Correct	3 ms	1788 KB	Output is correct
10	Correct	3 ms	1756 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	2473 ms	14832 KB	Output is correct
13	Correct	2917 ms	7480 KB	Output is correct
14	Correct	729 ms	4264 KB	Output is correct
15	Correct	2904 ms	7672 KB	Output is correct
16	Correct	2449 ms	10372 KB	Output is correct
17	Correct	1755 ms	7872 KB	Output is correct
18	Correct	3230 ms	10748 KB	Output is correct
19	Correct	2877 ms	10700 KB	Output is correct
20	Correct	3578 ms	10452 KB	Output is correct
21	Correct	3 ms	1784 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	4 ms	1776 KB	Output is correct
3	Correct	3 ms	1784 KB	Output is correct
4	Correct	3 ms	1788 KB	Output is correct
5	Correct	3 ms	1784 KB	Output is correct
6	Correct	3 ms	1784 KB	Output is correct
7	Correct	3 ms	1784 KB	Output is correct
8	Correct	3 ms	1784 KB	Output is correct
9	Correct	3 ms	1784 KB	Output is correct
10	Correct	3 ms	1784 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	2467 ms	15072 KB	Output is correct
13	Correct	1429 ms	13876 KB	Output is correct
14	Correct	2532 ms	10840 KB	Output is correct
15	Correct	2920 ms	10572 KB	Output is correct
16	Correct	1309 ms	8276 KB	Output is correct
17	Correct	2752 ms	10524 KB	Output is correct
18	Correct	3445 ms	10260 KB	Output is correct
19	Correct	2451 ms	13804 KB	Output is correct
20	Correct	2935 ms	7696 KB	Output is correct
21	Correct	729 ms	4496 KB	Output is correct
22	Correct	2910 ms	7748 KB	Output is correct
23	Correct	2416 ms	10704 KB	Output is correct
24	Correct	1736 ms	8192 KB	Output is correct
25	Correct	3267 ms	10768 KB	Output is correct
26	Correct	2874 ms	10912 KB	Output is correct
27	Correct	3560 ms	10600 KB	Output is correct
28	Correct	1353 ms	10792 KB	Output is correct
29	Correct	2720 ms	13684 KB	Output is correct
30	Correct	2917 ms	10392 KB	Output is correct
31	Correct	2595 ms	7992 KB	Output is correct
32	Correct	787 ms	4552 KB	Output is correct
33	Correct	1145 ms	4760 KB	Output is correct
34	Correct	2545 ms	10872 KB	Output is correct
35	Correct	1808 ms	8216 KB	Output is correct
36	Correct	3392 ms	11256 KB	Output is correct
37	Correct	2995 ms	11220 KB	Output is correct
38	Correct	3666 ms	10896 KB	Output is correct
39	Correct	2378 ms	8884 KB	Output is correct
40	Correct	3 ms	1788 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1784 KB	Output is correct
2	Correct	3 ms	1784 KB	Output is correct
3	Correct	3 ms	1784 KB	Output is correct
4	Correct	3 ms	1784 KB	Output is correct
5	Correct	3 ms	1784 KB	Output is correct
6	Correct	3 ms	1788 KB	Output is correct
7	Correct	3 ms	1784 KB	Output is correct
8	Correct	3 ms	1784 KB	Output is correct
9	Correct	3 ms	1784 KB	Output is correct
10	Correct	3 ms	1784 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	2474 ms	15292 KB	Output is correct
13	Correct	1427 ms	14332 KB	Output is correct
14	Correct	2538 ms	11144 KB	Output is correct
15	Correct	2890 ms	10872 KB	Output is correct
16	Correct	1321 ms	8684 KB	Output is correct
17	Correct	2724 ms	10920 KB	Output is correct
18	Correct	3443 ms	10316 KB	Output is correct
19	Correct	2454 ms	13848 KB	Output is correct
20	Correct	2917 ms	7848 KB	Output is correct
21	Correct	740 ms	4472 KB	Output is correct
22	Correct	2899 ms	7964 KB	Output is correct
23	Correct	2419 ms	10512 KB	Output is correct
24	Correct	1706 ms	8104 KB	Output is correct
25	Correct	3220 ms	11076 KB	Output is correct
26	Correct	2926 ms	11172 KB	Output is correct
27	Correct	3547 ms	10816 KB	Output is correct
28	Correct	1361 ms	10832 KB	Output is correct
29	Correct	2725 ms	14096 KB	Output is correct
30	Correct	2892 ms	10792 KB	Output is correct
31	Correct	2565 ms	8376 KB	Output is correct
32	Correct	801 ms	4732 KB	Output is correct
33	Correct	1141 ms	5124 KB	Output is correct
34	Correct	2547 ms	11156 KB	Output is correct
35	Correct	1816 ms	8412 KB	Output is correct
36	Correct	3380 ms	11320 KB	Output is correct
37	Correct	2983 ms	11564 KB	Output is correct
38	Correct	3655 ms	10916 KB	Output is correct
39	Correct	3768 ms	17880 KB	Output is correct
40	Correct	5017 ms	28188 KB	Output is correct
41	Correct	4749 ms	22348 KB	Output is correct
42	Correct	3822 ms	17244 KB	Output is correct
43	Correct	8964 ms	23048 KB	Output is correct
44	Correct	776 ms	12512 KB	Output is correct
45	Correct	2414 ms	17128 KB	Output is correct
46	Correct	7409 ms	27208 KB	Output is correct
47	Correct	7295 ms	27252 KB	Output is correct
48	Correct	11260 ms	26648 KB	Output is correct
49	Correct	3 ms	1784 KB	Output is correct