oj.uz

Submission #123988

# Submission time Handle Problem Language Result Execution time Memory
123988 2019-07-02T10:29:35 Z MAMBA Game (IOI13_game) C++17
63 / 100
 11814 ms 48452 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 = 16;

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 = 150;
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 + 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 37 ms 39548 KB Output is correct
2 Correct 40 ms 39672 KB Output is correct
3 Correct 41 ms 39676 KB Output is correct
4 Correct 37 ms 39544 KB Output is correct
5 Correct 38 ms 39624 KB Output is correct
6 Correct 39 ms 39672 KB Output is correct
7 Correct 37 ms 39644 KB Output is correct
8 Correct 37 ms 39544 KB Output is correct
9 Correct 39 ms 39676 KB Output is correct
10 Correct 39 ms 39688 KB Output is correct
11 Correct 39 ms 39756 KB Output is correct
12 Correct 37 ms 39544 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 39544 KB Output is correct
2 Correct 72 ms 39644 KB Output is correct
3 Correct 37 ms 39612 KB Output is correct
4 Correct 2234 ms 48016 KB Output is correct
5 Correct 1945 ms 48416 KB Output is correct
6 Correct 2246 ms 45056 KB Output is correct
7 Correct 2387 ms 44444 KB Output is correct
8 Correct 1208 ms 43988 KB Output is correct
9 Correct 2350 ms 44500 KB Output is correct
10 Correct 2667 ms 44056 KB Output is correct
11 Correct 37 ms 39644 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 39544 KB Output is correct
2 Correct 39 ms 39660 KB Output is correct
3 Correct 40 ms 39672 KB Output is correct
4 Correct 44 ms 39644 KB Output is correct
5 Correct 45 ms 39544 KB Output is correct
6 Correct 44 ms 39696 KB Output is correct
7 Correct 38 ms 39544 KB Output is correct
8 Correct 38 ms 39592 KB Output is correct
9 Correct 40 ms 39672 KB Output is correct
10 Correct 38 ms 39672 KB Output is correct
11 Correct 38 ms 39672 KB Output is correct
12 Correct 2529 ms 47596 KB Output is correct
13 Correct 3326 ms 43280 KB Output is correct
14 Correct 1241 ms 41392 KB Output is correct
15 Correct 3371 ms 43484 KB Output is correct
16 Correct 3883 ms 44148 KB Output is correct
17 Correct 1554 ms 43716 KB Output is correct
18 Correct 3137 ms 44528 KB Output is correct
19 Correct 2851 ms 44596 KB Output is correct
20 Correct 3079 ms 44280 KB Output is correct
21 Correct 37 ms 39672 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 40 ms 39688 KB Output is correct
3 Correct 41 ms 39780 KB Output is correct
4 Correct 37 ms 39672 KB Output is correct
5 Correct 38 ms 39560 KB Output is correct
6 Correct 39 ms 39672 KB Output is correct
7 Correct 37 ms 39692 KB Output is correct
8 Correct 38 ms 39548 KB Output is correct
9 Correct 39 ms 39676 KB Output is correct
10 Correct 38 ms 39672 KB Output is correct
11 Correct 39 ms 39672 KB Output is correct
12 Correct 2254 ms 47828 KB Output is correct
13 Correct 1936 ms 48136 KB Output is correct
14 Correct 2271 ms 44728 KB Output is correct
15 Correct 2425 ms 44596 KB Output is correct
16 Correct 1211 ms 44928 KB Output is correct
17 Correct 2356 ms 45544 KB Output is correct
18 Correct 2644 ms 44544 KB Output is correct
19 Correct 2498 ms 47960 KB Output is correct
20 Correct 3328 ms 43104 KB Output is correct
21 Correct 1251 ms 40904 KB Output is correct
22 Correct 3476 ms 43072 KB Output is correct
23 Correct 3885 ms 43660 KB Output is correct
24 Correct 1552 ms 43008 KB Output is correct
25 Correct 3146 ms 43996 KB Output is correct
26 Correct 2867 ms 44140 KB Output is correct
27 Correct 3079 ms 43668 KB Output is correct
28 Incorrect 11736 ms 48064 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39544 KB Output is correct
2 Correct 39 ms 39728 KB Output is correct
3 Correct 41 ms 39700 KB Output is correct
4 Correct 37 ms 39676 KB Output is correct
5 Correct 37 ms 39548 KB Output is correct
6 Correct 39 ms 39692 KB Output is correct
7 Correct 37 ms 39544 KB Output is correct
8 Correct 37 ms 39636 KB Output is correct
9 Correct 46 ms 39672 KB Output is correct
10 Correct 38 ms 39676 KB Output is correct
11 Correct 38 ms 39672 KB Output is correct
12 Correct 2224 ms 46392 KB Output is correct
13 Correct 1926 ms 46584 KB Output is correct
14 Correct 2272 ms 43476 KB Output is correct
15 Correct 2391 ms 43336 KB Output is correct
16 Correct 1231 ms 43000 KB Output is correct
17 Correct 2372 ms 43572 KB Output is correct
18 Correct 2669 ms 42936 KB Output is correct
19 Correct 2537 ms 46524 KB Output is correct
20 Correct 3316 ms 42364 KB Output is correct
21 Correct 1240 ms 40572 KB Output is correct
22 Correct 3487 ms 42424 KB Output is correct
23 Correct 3889 ms 43124 KB Output is correct
24 Correct 1550 ms 42640 KB Output is correct
25 Correct 3161 ms 43696 KB Output is correct
26 Correct 2819 ms 43564 KB Output is correct
27 Correct 3094 ms 42944 KB Output is correct
28 Incorrect 11814 ms 48452 KB Output isn't correct
29 Halted 0 ms 0 KB -