oj.uz

Submission #124000

# Submission time Handle Problem Language Result Execution time Memory
124000 2019-07-02T10:39:27 Z MAMBA Game (IOI13_game) C++17
100 / 100
 9621 ms 59604 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 47 ms 47992 KB Output is correct
3 Correct 49 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 47 ms 47864 KB Output is correct
7 Correct 53 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 55 ms 47992 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 46 ms 47956 KB Output is correct
12 Correct 45 ms 47900 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47952 KB Output is correct
2 Correct 44 ms 47888 KB Output is correct
3 Correct 44 ms 47992 KB Output is correct
4 Correct 2656 ms 56524 KB Output is correct
5 Correct 2413 ms 56784 KB Output is correct
6 Correct 2810 ms 53440 KB Output is correct
7 Correct 2894 ms 53292 KB Output is correct
8 Correct 1508 ms 52856 KB Output is correct
9 Correct 2866 ms 53416 KB Output is correct
10 Correct 3247 ms 52928 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47992 KB Output is correct
2 Correct 49 ms 47864 KB Output is correct
3 Correct 49 ms 47964 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 48 ms 47964 KB Output is correct
7 Correct 45 ms 47940 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 56 ms 47864 KB Output is correct
10 Correct 50 ms 47996 KB Output is correct
11 Correct 47 ms 47864 KB Output is correct
12 Correct 2926 ms 56604 KB Output is correct
13 Correct 3668 ms 52156 KB Output is correct
14 Correct 1609 ms 49788 KB Output is correct
15 Correct 3662 ms 52272 KB Output is correct
16 Correct 4282 ms 53148 KB Output is correct
17 Correct 1876 ms 52332 KB Output is correct
18 Correct 3594 ms 53572 KB Output is correct
19 Correct 3406 ms 53612 KB Output is correct
20 Correct 3684 ms 53300 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 44 ms 47864 KB Output is correct
2 Correct 46 ms 47964 KB Output is correct
3 Correct 47 ms 47992 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 45 ms 48108 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 44 ms 47868 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 53 ms 47992 KB Output is correct
12 Correct 2652 ms 56792 KB Output is correct
13 Correct 2362 ms 57056 KB Output is correct
14 Correct 2820 ms 53860 KB Output is correct
15 Correct 2965 ms 53548 KB Output is correct
16 Correct 1499 ms 53196 KB Output is correct
17 Correct 2854 ms 53984 KB Output is correct
18 Correct 3230 ms 53500 KB Output is correct
19 Correct 2931 ms 56968 KB Output is correct
20 Correct 3672 ms 52436 KB Output is correct
21 Correct 1607 ms 49784 KB Output is correct
22 Correct 3658 ms 52532 KB Output is correct
23 Correct 4272 ms 53496 KB Output is correct
24 Correct 1881 ms 52356 KB Output is correct
25 Correct 3610 ms 53552 KB Output is correct
26 Correct 3397 ms 53680 KB Output is correct
27 Correct 3703 ms 53328 KB Output is correct
28 Correct 1082 ms 52692 KB Output is correct
29 Correct 3018 ms 56244 KB Output is correct
30 Correct 4221 ms 53380 KB Output is correct
31 Correct 3705 ms 52652 KB Output is correct
32 Correct 1665 ms 50040 KB Output is correct
33 Correct 1873 ms 50168 KB Output is correct
34 Correct 4355 ms 53500 KB Output is correct
35 Correct 1989 ms 52600 KB Output is correct
36 Correct 3679 ms 53752 KB Output is correct
37 Correct 3380 ms 53904 KB Output is correct
38 Correct 3732 ms 53456 KB Output is correct
39 Correct 2710 ms 53216 KB Output is correct
40 Correct 45 ms 47864 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 47 ms 47864 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 44 ms 47908 KB Output is correct
5 Correct 44 ms 47836 KB Output is correct
6 Correct 46 ms 47908 KB Output is correct
7 Correct 49 ms 47916 KB Output is correct
8 Correct 53 ms 47884 KB Output is correct
9 Correct 47 ms 47864 KB Output is correct
10 Correct 46 ms 48024 KB Output is correct
11 Correct 45 ms 47964 KB Output is correct
12 Correct 2647 ms 57952 KB Output is correct
13 Correct 2386 ms 58220 KB Output is correct
14 Correct 2822 ms 55016 KB Output is correct
15 Correct 2896 ms 55044 KB Output is correct
16 Correct 1504 ms 54608 KB Output is correct
17 Correct 2859 ms 55416 KB Output is correct
18 Correct 3233 ms 54284 KB Output is correct
19 Correct 2931 ms 57936 KB Output is correct
20 Correct 3629 ms 52288 KB Output is correct
21 Correct 1613 ms 49860 KB Output is correct
22 Correct 3658 ms 52432 KB Output is correct
23 Correct 4274 ms 53460 KB Output is correct
24 Correct 1890 ms 52384 KB Output is correct
25 Correct 3606 ms 53608 KB Output is correct
26 Correct 3373 ms 53932 KB Output is correct
27 Correct 3675 ms 53260 KB Output is correct
28 Correct 1084 ms 52864 KB Output is correct
29 Correct 3022 ms 56736 KB Output is correct
30 Correct 4200 ms 53820 KB Output is correct
31 Correct 3731 ms 53192 KB Output is correct
32 Correct 1670 ms 50692 KB Output is correct
33 Correct 1886 ms 50452 KB Output is correct
34 Correct 4388 ms 53732 KB Output is correct
35 Correct 1986 ms 52688 KB Output is correct
36 Correct 3678 ms 53932 KB Output is correct
37 Correct 3384 ms 54260 KB Output is correct
38 Correct 3729 ms 54112 KB Output is correct
39 Correct 2074 ms 56416 KB Output is correct
40 Correct 5671 ms 59604 KB Output is correct
41 Correct 8678 ms 57316 KB Output is correct
42 Correct 7283 ms 55752 KB Output is correct
43 Correct 9621 ms 57704 KB Output is correct
44 Correct 3259 ms 51308 KB Output is correct
45 Correct 2710 ms 54244 KB Output is correct
46 Correct 7135 ms 57900 KB Output is correct
47 Correct 7102 ms 57796 KB Output is correct
48 Correct 7982 ms 57224 KB Output is correct
49 Correct 45 ms 47864 KB Output is correct