oj.uz

Submission #123946

# Submission time Handle Problem Language Result Execution time Memory
123946 2019-07-02T09:58:26 Z MAMBA Game (IOI13_game) C++17
37 / 100
 3251 ms 55736 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 , 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 45 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 47840 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 50 ms 48120 KB Output is correct
10 Correct 47 ms 47864 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 44 ms 47868 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 44 ms 47836 KB Output is correct
3 Correct 44 ms 47876 KB Output is correct
4 Correct 2638 ms 55392 KB Output is correct
5 Correct 2354 ms 55672 KB Output is correct
6 Correct 2828 ms 52276 KB Output is correct
7 Correct 2971 ms 52272 KB Output is correct
8 Correct 1526 ms 51548 KB Output is correct
9 Correct 2861 ms 52432 KB Output is correct
10 Correct 3238 ms 52080 KB Output is correct
11 Correct 44 ms 47864 KB Output is correct

Subtask #3
0 / 26.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 48 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 47864 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47992 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 45 ms 47912 KB Output is correct
12 Incorrect 2904 ms 55504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47864 KB Output is correct
2 Correct 47 ms 47868 KB Output is correct
3 Correct 48 ms 47992 KB Output is correct
4 Correct 44 ms 47992 KB Output is correct
5 Correct 44 ms 47916 KB Output is correct
6 Correct 47 ms 47992 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 45 ms 47992 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47868 KB Output is correct
11 Correct 46 ms 47972 KB Output is correct
12 Correct 2653 ms 55468 KB Output is correct
13 Correct 2378 ms 55736 KB Output is correct
14 Correct 2807 ms 52676 KB Output is correct
15 Correct 2887 ms 52168 KB Output is correct
16 Correct 1502 ms 51576 KB Output is correct
17 Correct 2853 ms 52288 KB Output is correct
18 Correct 3249 ms 52044 KB Output is correct
19 Incorrect 2917 ms 55640 KB Output isn't correct
20 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 47884 KB Output is correct
3 Correct 47 ms 47992 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 46 ms 47912 KB Output is correct
6 Correct 47 ms 47880 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 49 ms 47964 KB Output is correct
9 Correct 46 ms 47864 KB Output is correct
10 Correct 45 ms 47864 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 2645 ms 55328 KB Output is correct
13 Correct 2377 ms 55644 KB Output is correct
14 Correct 2891 ms 52464 KB Output is correct
15 Correct 2886 ms 52204 KB Output is correct
16 Correct 1530 ms 51576 KB Output is correct
17 Correct 2857 ms 52364 KB Output is correct
18 Correct 3251 ms 51908 KB Output is correct
19 Incorrect 2918 ms 55456 KB Output isn't correct
20 Halted 0 ms 0 KB -