oj.uz

Submission #123996

# Submission time Handle Problem Language Result Execution time Memory
123996 2019-07-02T10:34:04 Z MAMBA Game (IOI13_game) C++17
100 / 100
 9683 ms 67860 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;

const int LG = 20;

ll gcd(ll a , ll b) { return a ? gcd(b % a , a) : b; }

struct rmq {
	vector<ll> arr[LG], G;
	inline rmq() {}
 	inline 	rmq(ll* L , ll* R) {
		int sz = R - L;
		G.resize(sz + 1);
		int me = 0;
		rep(i ,1 , sz + 1) {
			G[i] = me;
			if ((2 << me) == i) me++;
		}
		rep(i , 0 , LG)
			arr[i].resize(sz);
		rep(i , 0 , sz)
			arr[0][i] = *(L + i);
		rep(i , 1 , LG)
			for (int j = 0, k = 1 << (i - 1); j < sz; j++, k++)
				arr[i][j] = gcd(arr[i - 1][j] , k >= sz ? 0 : arr[i - 1][k]);
	}
	inline ll ask(int l , int r) {
		if (l == r) return 0;
		
		int sz = G[r - l];
		return gcd(arr[sz][l] , arr[sz][r - (1 << sz)]);
	}
};

const int sq = 200;
const int N = 22010 * 4;

int junk;
vector<pair<pii , ll>> a[N];
map<pii , ll> mp;
vector<int> b[N];

rmq ask[N];

ll tmp[N];

void build(int id) {
	b[id].resize(a[id].size());
	sort(all(a[id]));
	iota(all(b[id]) , 0);
	sort(all(b[id]) , [&id](int l , int r) { return a[id][l].first.second < a[id][r].first.second; });
	rep(i , 0 , a[id].size())
		tmp[i] = a[id][b[id][i]].second;
	ask[id] = rmq(tmp , tmp + a[id].size());
}

void init(int R, int C) {
	if (mp.size()) assert(0);
}

void update(int P, int Q, long long K) {
	junk++;
	pii me(P , Q);
	if (mp.count(me)) {
		for (int i = 0;;i++)
			if (me <= a[i].back().first) {
				for (auto &e : a[i])
					if (e.first == me)
						e.second = K;
				build(i);
				break;
			}
	}	
	else {
		for (int i = 0;;i++)
			if (a[i].empty() || me <= a[i].back().first) {
				a[i].pb({me , K});
				build(i);
				break;
			}
	}
	mp[me] = K;
	if (junk % sq == 0) {
		int cnt = 0;
		int ptr = 0;
		a[0].clear();
		for (auto e : mp) {
			a[ptr].pb(e);
			cnt++;
			if (cnt % sq == 0) {
				cnt = 0;
				ptr++;
				a[ptr].clear();
			}
		}
      rep(i , ptr + 1, ptr + sq + 10) a[i].clear();
		rep(i , 0 , ptr + 10)
			build(i);
	}
}	

long long calculate(int P, int Q, int U, int V) {
	ll res = 0;
	int go = 0;
	for(;;go++) {
		if (a[go].empty()) return 0;
		if (P <= a[go].back().first.first) {
			for (auto e : a[go])
				if (e.first.first >= P && e.first.first <= U && e.first.second >= Q && e.first.second <= V)
					res = gcd(res , e.second);
			break;
		}
	}
	go++;
	for (;;go++) {
		if (a[go].empty()) return res;
		if (U < a[go].back().first.first) {
			for (auto e : a[go])
				if (e.first.first >= P && e.first.first <= U && e.first.second >= Q && e.first.second <= V)
					res = gcd(res , e.second);
			return res;
		}
		int l = lower_bound(all(b[go]) , Q , [&go](int l , int r) { return a[go][l].first.second < r; }) - b[go].begin();
		int r = upper_bound(all(b[go]) , V , [&go](int l , int r) { return l < a[go][r].first.second; }) - b[go].begin();
		res = gcd(res , ask[go].ask(l , r));
	}
	return -1;
}

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 45 ms 47864 KB Output is correct
2 Correct 48 ms 47864 KB Output is correct
3 Correct 49 ms 47992 KB Output is correct
4 Correct 44 ms 47992 KB Output is correct
5 Correct 44 ms 47992 KB Output is correct
6 Correct 48 ms 47992 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47968 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47868 KB Output is correct
12 Correct 44 ms 47864 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 44 ms 47872 KB Output is correct
3 Correct 44 ms 47868 KB Output is correct
4 Correct 2638 ms 56064 KB Output is correct
5 Correct 2364 ms 56236 KB Output is correct
6 Correct 2808 ms 52844 KB Output is correct
7 Correct 2947 ms 52640 KB Output is correct
8 Correct 1501 ms 52088 KB Output is correct
9 Correct 2880 ms 52760 KB Output is correct
10 Correct 3233 ms 52256 KB Output is correct
11 Correct 45 ms 47992 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47868 KB Output is correct
2 Correct 47 ms 47992 KB Output is correct
3 Correct 49 ms 47964 KB Output is correct
4 Correct 44 ms 47868 KB Output is correct
5 Correct 45 ms 47864 KB Output is correct
6 Correct 47 ms 47964 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 2929 ms 55796 KB Output is correct
13 Correct 3635 ms 51536 KB Output is correct
14 Correct 1607 ms 49120 KB Output is correct
15 Correct 3657 ms 51536 KB Output is correct
16 Correct 4288 ms 52580 KB Output is correct
17 Correct 1875 ms 51604 KB Output is correct
18 Correct 3600 ms 52956 KB Output is correct
19 Correct 3377 ms 52976 KB Output is correct
20 Correct 3678 ms 52416 KB Output is correct
21 Correct 45 ms 47864 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 47 ms 47984 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 54 ms 47864 KB Output is correct
5 Correct 55 ms 47864 KB Output is correct
6 Correct 57 ms 47992 KB Output is correct
7 Correct 51 ms 47896 KB Output is correct
8 Correct 45 ms 47992 KB Output is correct
9 Correct 47 ms 47864 KB Output is correct
10 Correct 54 ms 47864 KB Output is correct
11 Correct 46 ms 47920 KB Output is correct
12 Correct 2638 ms 55844 KB Output is correct
13 Correct 2369 ms 56068 KB Output is correct
14 Correct 2801 ms 52860 KB Output is correct
15 Correct 2911 ms 52512 KB Output is correct
16 Correct 1503 ms 52344 KB Output is correct
17 Correct 2851 ms 53184 KB Output is correct
18 Correct 3246 ms 52476 KB Output is correct
19 Correct 2902 ms 56056 KB Output is correct
20 Correct 3628 ms 51628 KB Output is correct
21 Correct 1611 ms 49016 KB Output is correct
22 Correct 3657 ms 51644 KB Output is correct
23 Correct 4275 ms 52556 KB Output is correct
24 Correct 1889 ms 51576 KB Output is correct
25 Correct 3589 ms 52924 KB Output is correct
26 Correct 3365 ms 52948 KB Output is correct
27 Correct 3690 ms 52492 KB Output is correct
28 Correct 1086 ms 51448 KB Output is correct
29 Correct 3041 ms 65212 KB Output is correct
30 Correct 4289 ms 58964 KB Output is correct
31 Correct 3701 ms 58224 KB Output is correct
32 Correct 1733 ms 57792 KB Output is correct
33 Correct 1873 ms 57976 KB Output is correct
34 Correct 4302 ms 58992 KB Output is correct
35 Correct 2009 ms 61092 KB Output is correct
36 Correct 3671 ms 63068 KB Output is correct
37 Correct 3376 ms 63228 KB Output is correct
38 Correct 3764 ms 62732 KB Output is correct
39 Correct 2720 ms 62312 KB Output is correct
40 Correct 44 ms 47864 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47880 KB Output is correct
2 Correct 47 ms 47996 KB Output is correct
3 Correct 48 ms 47992 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 45 ms 47864 KB Output is correct
6 Correct 49 ms 47964 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 47 ms 47848 KB Output is correct
9 Correct 52 ms 47992 KB Output is correct
10 Correct 54 ms 47992 KB Output is correct
11 Correct 45 ms 47836 KB Output is correct
12 Correct 2627 ms 55656 KB Output is correct
13 Correct 2347 ms 55900 KB Output is correct
14 Correct 2784 ms 52656 KB Output is correct
15 Correct 2879 ms 52428 KB Output is correct
16 Correct 1506 ms 51960 KB Output is correct
17 Correct 2852 ms 52636 KB Output is correct
18 Correct 3248 ms 52020 KB Output is correct
19 Correct 2907 ms 55588 KB Output is correct
20 Correct 3645 ms 51136 KB Output is correct
21 Correct 1603 ms 48720 KB Output is correct
22 Correct 3657 ms 51260 KB Output is correct
23 Correct 4285 ms 52292 KB Output is correct
24 Correct 1881 ms 51404 KB Output is correct
25 Correct 3599 ms 52808 KB Output is correct
26 Correct 3381 ms 52688 KB Output is correct
27 Correct 3691 ms 52308 KB Output is correct
28 Correct 1078 ms 51152 KB Output is correct
29 Correct 3043 ms 65128 KB Output is correct
30 Correct 4237 ms 58964 KB Output is correct
31 Correct 3704 ms 58336 KB Output is correct
32 Correct 1664 ms 57984 KB Output is correct
33 Correct 1874 ms 58104 KB Output is correct
34 Correct 4325 ms 59072 KB Output is correct
35 Correct 2019 ms 60968 KB Output is correct
36 Correct 3696 ms 63116 KB Output is correct
37 Correct 3434 ms 63256 KB Output is correct
38 Correct 3734 ms 62680 KB Output is correct
39 Correct 2087 ms 64988 KB Output is correct
40 Correct 5770 ms 67860 KB Output is correct
41 Correct 8741 ms 62360 KB Output is correct
42 Correct 7277 ms 60568 KB Output is correct
43 Correct 9683 ms 62580 KB Output is correct
44 Correct 3241 ms 58424 KB Output is correct
45 Correct 2719 ms 62420 KB Output is correct
46 Correct 7175 ms 66656 KB Output is correct
47 Correct 7145 ms 66416 KB Output is correct
48 Correct 8020 ms 66148 KB Output is correct
49 Correct 44 ms 47992 KB Output is correct