oj.uz

Submission #123984

# Submission time Handle Problem Language Result Execution time Memory
123984 2019-07-02T10:26:16 Z MAMBA Game (IOI13_game) C++17
63 / 100
 13000 ms 68228 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 = 300;
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 46 ms 48004 KB Output is correct
2 Correct 48 ms 48004 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 43 ms 47864 KB Output is correct
6 Correct 46 ms 47984 KB Output is correct
7 Correct 43 ms 47864 KB Output is correct
8 Correct 43 ms 47864 KB Output is correct
9 Correct 45 ms 47864 KB Output is correct
10 Correct 44 ms 47868 KB Output is correct
11 Correct 45 ms 47992 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 47916 KB Output is correct
2 Correct 45 ms 47836 KB Output is correct
3 Correct 45 ms 47864 KB Output is correct
4 Correct 3440 ms 57332 KB Output is correct
5 Correct 3153 ms 57644 KB Output is correct
6 Correct 3719 ms 54332 KB Output is correct
7 Correct 3777 ms 53496 KB Output is correct
8 Correct 1989 ms 52368 KB Output is correct
9 Correct 3779 ms 53656 KB Output is correct
10 Correct 4246 ms 53060 KB Output is correct
11 Correct 44 ms 47864 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47912 KB Output is correct
2 Correct 47 ms 47864 KB Output is correct
3 Correct 59 ms 47888 KB Output is correct
4 Correct 56 ms 47908 KB Output is correct
5 Correct 45 ms 47912 KB Output is correct
6 Correct 47 ms 47864 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 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 3696 ms 56880 KB Output is correct
13 Correct 4227 ms 55932 KB Output is correct
14 Correct 2146 ms 53368 KB Output is correct
15 Correct 4290 ms 56456 KB Output is correct
16 Correct 5302 ms 57752 KB Output is correct
17 Correct 2488 ms 56532 KB Output is correct
18 Correct 4545 ms 58864 KB Output is correct
19 Correct 4382 ms 58760 KB Output is correct
20 Correct 4844 ms 58552 KB Output is correct
21 Correct 45 ms 47964 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47892 KB Output is correct
2 Correct 46 ms 47864 KB Output is correct
3 Correct 48 ms 47964 KB Output is correct
4 Correct 43 ms 47928 KB Output is correct
5 Correct 47 ms 47868 KB Output is correct
6 Correct 53 ms 47952 KB Output is correct
7 Correct 44 ms 47868 KB Output is correct
8 Correct 43 ms 47864 KB Output is correct
9 Correct 45 ms 47964 KB Output is correct
10 Correct 44 ms 47864 KB Output is correct
11 Correct 45 ms 47836 KB Output is correct
12 Correct 3420 ms 56796 KB Output is correct
13 Correct 3213 ms 57556 KB Output is correct
14 Correct 3729 ms 54168 KB Output is correct
15 Correct 3780 ms 53852 KB Output is correct
16 Correct 2000 ms 53048 KB Output is correct
17 Correct 3782 ms 54368 KB Output is correct
18 Correct 4292 ms 53820 KB Output is correct
19 Correct 3664 ms 57464 KB Output is correct
20 Correct 4240 ms 55968 KB Output is correct
21 Correct 2152 ms 53332 KB Output is correct
22 Correct 4252 ms 56492 KB Output is correct
23 Correct 5279 ms 57688 KB Output is correct
24 Correct 2468 ms 56436 KB Output is correct
25 Correct 4534 ms 58968 KB Output is correct
26 Correct 4366 ms 58888 KB Output is correct
27 Correct 4896 ms 58832 KB Output is correct
28 Execution timed out 13070 ms 68228 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 47 ms 47964 KB Output is correct
3 Correct 56 ms 47864 KB Output is correct
4 Correct 45 ms 47920 KB Output is correct
5 Correct 44 ms 47840 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 45 ms 47812 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 45 ms 47992 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 3439 ms 57508 KB Output is correct
13 Correct 3140 ms 57900 KB Output is correct
14 Correct 3760 ms 54484 KB Output is correct
15 Correct 3765 ms 54248 KB Output is correct
16 Correct 1990 ms 53172 KB Output is correct
17 Correct 3792 ms 54384 KB Output is correct
18 Correct 4278 ms 54764 KB Output is correct
19 Correct 3674 ms 58324 KB Output is correct
20 Correct 4221 ms 55804 KB Output is correct
21 Correct 2167 ms 53348 KB Output is correct
22 Correct 4265 ms 56288 KB Output is correct
23 Correct 5299 ms 57612 KB Output is correct
24 Correct 2482 ms 56464 KB Output is correct
25 Correct 4578 ms 58836 KB Output is correct
26 Correct 4362 ms 58824 KB Output is correct
27 Correct 4835 ms 58620 KB Output is correct
28 Execution timed out 13041 ms 67588 KB Time limit exceeded
29 Halted 0 ms 0 KB -