oj.uz

Submission #123941

# Submission time Handle Problem Language Result Execution time Memory
123941 2019-07-02T09:56:37 Z MAMBA Game (IOI13_game) C++17
37 / 100
 3245 ms 20212 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;

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 , 0 , ptr + 1)
			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 12 ms 12152 KB Output is correct
2 Correct 15 ms 12280 KB Output is correct
3 Correct 15 ms 12284 KB Output is correct
4 Correct 12 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 12 ms 12152 KB Output is correct
8 Correct 12 ms 12280 KB Output is correct
9 Correct 13 ms 12280 KB Output is correct
10 Correct 12 ms 12280 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Correct 12 ms 12280 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12280 KB Output is correct
2 Correct 11 ms 12152 KB Output is correct
3 Correct 12 ms 12280 KB Output is correct
4 Correct 2627 ms 19672 KB Output is correct
5 Correct 2355 ms 20048 KB Output is correct
6 Correct 2752 ms 16732 KB Output is correct
7 Correct 2855 ms 16584 KB Output is correct
8 Correct 1472 ms 15864 KB Output is correct
9 Correct 2838 ms 16744 KB Output is correct
10 Correct 3196 ms 16200 KB Output is correct
11 Correct 12 ms 12152 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 15 ms 12280 KB Output is correct
3 Correct 15 ms 12280 KB Output is correct
4 Correct 12 ms 12156 KB Output is correct
5 Correct 12 ms 12280 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 12 ms 12252 KB Output is correct
8 Correct 11 ms 12152 KB Output is correct
9 Correct 13 ms 12280 KB Output is correct
10 Correct 15 ms 12200 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Incorrect 2897 ms 19744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12264 KB Output is correct
2 Correct 15 ms 12252 KB Output is correct
3 Correct 16 ms 12280 KB Output is correct
4 Correct 12 ms 12152 KB Output is correct
5 Correct 12 ms 12156 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 12 ms 12152 KB Output is correct
8 Correct 12 ms 12152 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 12 ms 12280 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Correct 2606 ms 19840 KB Output is correct
13 Correct 2343 ms 20020 KB Output is correct
14 Correct 2781 ms 16764 KB Output is correct
15 Correct 2884 ms 16552 KB Output is correct
16 Correct 1468 ms 15736 KB Output is correct
17 Correct 2815 ms 16788 KB Output is correct
18 Correct 3245 ms 16168 KB Output is correct
19 Incorrect 2897 ms 20020 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 15 ms 12280 KB Output is correct
4 Correct 12 ms 12280 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 12 ms 12280 KB Output is correct
8 Correct 12 ms 12280 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 13 ms 12252 KB Output is correct
11 Correct 13 ms 12292 KB Output is correct
12 Correct 2603 ms 19704 KB Output is correct
13 Correct 2332 ms 20212 KB Output is correct
14 Correct 2769 ms 16808 KB Output is correct
15 Correct 2839 ms 16616 KB Output is correct
16 Correct 1498 ms 15808 KB Output is correct
17 Correct 2845 ms 16868 KB Output is correct
18 Correct 3220 ms 16440 KB Output is correct
19 Incorrect 2893 ms 19864 KB Output isn't correct
20 Halted 0 ms 0 KB -