oj.uz

Submission #123800

# Submission time Handle Problem Language Result Execution time Memory
123800 2019-07-02T07:03:21 Z Mahdi_Jfri Game (IOI13_game) C++14
80 / 100
 3787 ms 20780 KB 
//#include "grader.h"
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2.3e4 + 20;
const int maxb = 15;
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 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 3 ms 1660 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1656 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 3 ms 1656 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 2471 ms 11752 KB Output is correct
5 Correct 1390 ms 11764 KB Output is correct
6 Correct 2498 ms 8400 KB Output is correct
7 Correct 2891 ms 8220 KB Output is correct
8 Correct 1342 ms 6284 KB Output is correct
9 Correct 2768 ms 8308 KB Output is correct
10 Correct 3425 ms 7960 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1656 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1660 KB Output is correct
11 Correct 4 ms 1656 KB Output is correct
12 Correct 2454 ms 11764 KB Output is correct
13 Correct 2893 ms 5920 KB Output is correct
14 Correct 729 ms 2872 KB Output is correct
15 Correct 2897 ms 6060 KB Output is correct
16 Correct 2397 ms 8380 KB Output is correct
17 Correct 1706 ms 6032 KB Output is correct
18 Correct 3320 ms 8552 KB Output is correct
19 Correct 2874 ms 8676 KB Output is correct
20 Correct 3523 ms 8228 KB Output is correct
21 Correct 3 ms 1656 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1660 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1656 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1656 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 2451 ms 11644 KB Output is correct
13 Correct 1408 ms 11712 KB Output is correct
14 Correct 2523 ms 8704 KB Output is correct
15 Correct 2895 ms 8380 KB Output is correct
16 Correct 1307 ms 6468 KB Output is correct
17 Correct 2753 ms 8680 KB Output is correct
18 Correct 3415 ms 8312 KB Output is correct
19 Correct 2453 ms 11924 KB Output is correct
20 Correct 2960 ms 6264 KB Output is correct
21 Correct 732 ms 3128 KB Output is correct
22 Correct 2914 ms 6316 KB Output is correct
23 Correct 2406 ms 8564 KB Output is correct
24 Correct 1695 ms 6528 KB Output is correct
25 Correct 3258 ms 9048 KB Output is correct
26 Correct 2834 ms 9140 KB Output is correct
27 Correct 3515 ms 8484 KB Output is correct
28 Correct 1336 ms 8952 KB Output is correct
29 Correct 2689 ms 11884 KB Output is correct
30 Correct 2878 ms 8592 KB Output is correct
31 Correct 2559 ms 6424 KB Output is correct
32 Correct 795 ms 3324 KB Output is correct
33 Correct 1153 ms 3320 KB Output is correct
34 Correct 2551 ms 8856 KB Output is correct
35 Correct 1821 ms 6648 KB Output is correct
36 Correct 3452 ms 9348 KB Output is correct
37 Correct 2997 ms 9452 KB Output is correct
38 Correct 3626 ms 8864 KB Output is correct
39 Correct 2345 ms 6956 KB Output is correct
40 Correct 3 ms 1656 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1704 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 4 ms 1656 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1656 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1656 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 2437 ms 12320 KB Output is correct
13 Correct 1388 ms 12156 KB Output is correct
14 Correct 2528 ms 8776 KB Output is correct
15 Correct 2877 ms 8676 KB Output is correct
16 Correct 1315 ms 6700 KB Output is correct
17 Correct 2702 ms 8780 KB Output is correct
18 Correct 3471 ms 8056 KB Output is correct
19 Correct 2432 ms 11484 KB Output is correct
20 Correct 2902 ms 5860 KB Output is correct
21 Correct 728 ms 2908 KB Output is correct
22 Correct 2978 ms 6104 KB Output is correct
23 Correct 2395 ms 8436 KB Output is correct
24 Correct 1689 ms 6264 KB Output is correct
25 Correct 3226 ms 8688 KB Output is correct
26 Correct 2853 ms 8856 KB Output is correct
27 Correct 3515 ms 8180 KB Output is correct
28 Correct 1354 ms 8440 KB Output is correct
29 Correct 2722 ms 11704 KB Output is correct
30 Correct 2879 ms 9044 KB Output is correct
31 Correct 2576 ms 6972 KB Output is correct
32 Correct 783 ms 3668 KB Output is correct
33 Correct 1138 ms 3972 KB Output is correct
34 Correct 2580 ms 9820 KB Output is correct
35 Correct 1795 ms 7312 KB Output is correct
36 Correct 3318 ms 9976 KB Output is correct
37 Correct 2919 ms 10116 KB Output is correct
38 Correct 3787 ms 9432 KB Output is correct
39 Incorrect 3667 ms 20780 KB Output isn't correct
40 Halted 0 ms 0 KB -