oj.uz

Submission #123986

# Submission time Handle Problem Language Result Execution time Memory
123986 2019-07-02T10:27:29 Z MAMBA Game (IOI13_game) C++17
63 / 100
 12406 ms 58212 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 = 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 45 ms 47864 KB Output is correct
2 Correct 48 ms 47864 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 46 ms 47864 KB Output is correct
5 Correct 46 ms 47864 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 55 ms 47864 KB Output is correct
10 Correct 49 ms 47984 KB Output is correct
11 Correct 56 ms 47992 KB Output is correct
12 Correct 46 ms 47916 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 47852 KB Output is correct
2 Correct 54 ms 47868 KB Output is correct
3 Correct 45 ms 47864 KB Output is correct
4 Correct 2355 ms 55884 KB Output is correct
5 Correct 2085 ms 56108 KB Output is correct
6 Correct 2387 ms 52832 KB Output is correct
7 Correct 2496 ms 52280 KB Output is correct
8 Correct 1278 ms 51616 KB Output is correct
9 Correct 2496 ms 52516 KB Output is correct
10 Correct 2786 ms 51960 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 44 ms 47864 KB Output is correct
2 Correct 46 ms 47948 KB Output is correct
3 Correct 48 ms 47876 KB Output is correct
4 Correct 45 ms 47904 KB Output is correct
5 Correct 45 ms 47900 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 45 ms 47928 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 47 ms 47964 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 2678 ms 55500 KB Output is correct
13 Correct 3480 ms 51296 KB Output is correct
14 Correct 1370 ms 49136 KB Output is correct
15 Correct 3540 ms 51392 KB Output is correct
16 Correct 4024 ms 52332 KB Output is correct
17 Correct 1617 ms 51444 KB Output is correct
18 Correct 3278 ms 52668 KB Output is correct
19 Correct 2961 ms 52680 KB Output is correct
20 Correct 3192 ms 52204 KB Output is correct
21 Correct 43 ms 47868 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 46 ms 47864 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 53 ms 47864 KB Output is correct
5 Correct 45 ms 47912 KB Output is correct
6 Correct 53 ms 47864 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 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 2359 ms 55660 KB Output is correct
13 Correct 2085 ms 55436 KB Output is correct
14 Correct 2441 ms 52172 KB Output is correct
15 Correct 2563 ms 51856 KB Output is correct
16 Correct 1298 ms 51168 KB Output is correct
17 Correct 2494 ms 52032 KB Output is correct
18 Correct 2769 ms 51496 KB Output is correct
19 Correct 2631 ms 55032 KB Output is correct
20 Correct 3478 ms 50792 KB Output is correct
21 Correct 1349 ms 48584 KB Output is correct
22 Correct 3491 ms 50828 KB Output is correct
23 Correct 4006 ms 51732 KB Output is correct
24 Correct 1613 ms 50920 KB Output is correct
25 Correct 3246 ms 52304 KB Output is correct
26 Correct 2994 ms 52360 KB Output is correct
27 Correct 3221 ms 51832 KB Output is correct
28 Incorrect 12358 ms 58212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 48 ms 47968 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 46 ms 47864 KB Output is correct
7 Correct 49 ms 47992 KB Output is correct
8 Correct 53 ms 47864 KB Output is correct
9 Correct 44 ms 47864 KB Output is correct
10 Correct 45 ms 47868 KB Output is correct
11 Correct 55 ms 47868 KB Output is correct
12 Correct 2384 ms 56716 KB Output is correct
13 Correct 2084 ms 56992 KB Output is correct
14 Correct 2401 ms 53952 KB Output is correct
15 Correct 2565 ms 53144 KB Output is correct
16 Correct 1278 ms 52540 KB Output is correct
17 Correct 2490 ms 53288 KB Output is correct
18 Correct 2805 ms 51480 KB Output is correct
19 Correct 2655 ms 54948 KB Output is correct
20 Correct 3473 ms 50808 KB Output is correct
21 Correct 1348 ms 48580 KB Output is correct
22 Correct 3518 ms 50892 KB Output is correct
23 Correct 4018 ms 51672 KB Output is correct
24 Correct 1614 ms 50864 KB Output is correct
25 Correct 3298 ms 52124 KB Output is correct
26 Correct 2992 ms 52192 KB Output is correct
27 Correct 3219 ms 51696 KB Output is correct
28 Incorrect 12406 ms 58180 KB Output isn't correct
29 Halted 0 ms 0 KB -