oj.uz

Submission #123956

# Submission time Handle Problem Language Result Execution time Memory
123956 2019-07-02T10:08:01 Z MAMBA Game (IOI13_game) C++17
37 / 100
 4344 ms 59204 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 , 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 46 ms 47864 KB Output is correct
2 Correct 47 ms 47864 KB Output is correct
3 Correct 50 ms 47992 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 46 ms 47836 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 45 ms 47836 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 47 ms 47992 KB Output is correct
10 Correct 47 ms 47992 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 46 ms 47864 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 46 ms 47960 KB Output is correct
3 Correct 45 ms 47864 KB Output is correct
4 Correct 3451 ms 58744 KB Output is correct
5 Correct 3232 ms 59204 KB Output is correct
6 Correct 3742 ms 55696 KB Output is correct
7 Correct 3804 ms 55296 KB Output is correct
8 Correct 2055 ms 54008 KB Output is correct
9 Correct 3817 ms 55432 KB Output is correct
10 Correct 4249 ms 55144 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 48 ms 47908 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 46 ms 47884 KB Output is correct
5 Correct 55 ms 47864 KB Output is correct
6 Correct 48 ms 47864 KB Output is correct
7 Correct 54 ms 47864 KB Output is correct
8 Correct 46 ms 47864 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 47 ms 47988 KB Output is correct
11 Correct 47 ms 47992 KB Output is correct
12 Incorrect 3722 ms 58468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47996 KB Output is correct
2 Correct 47 ms 47888 KB Output is correct
3 Correct 49 ms 47992 KB Output is correct
4 Correct 45 ms 47836 KB Output is correct
5 Correct 54 ms 47836 KB Output is correct
6 Correct 48 ms 47992 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 46 ms 47864 KB Output is correct
9 Correct 46 ms 47952 KB Output is correct
10 Correct 46 ms 47864 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 3451 ms 58680 KB Output is correct
13 Correct 3158 ms 59000 KB Output is correct
14 Correct 3797 ms 55800 KB Output is correct
15 Correct 3840 ms 55268 KB Output is correct
16 Correct 2032 ms 54028 KB Output is correct
17 Correct 3793 ms 55516 KB Output is correct
18 Correct 4279 ms 55196 KB Output is correct
19 Incorrect 3702 ms 58764 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47864 KB Output is correct
2 Correct 53 ms 47992 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 54 ms 47848 KB Output is correct
6 Correct 57 ms 47992 KB Output is correct
7 Correct 55 ms 47864 KB Output is correct
8 Correct 54 ms 47864 KB Output is correct
9 Correct 47 ms 47864 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 48 ms 47944 KB Output is correct
12 Correct 3424 ms 58724 KB Output is correct
13 Correct 3146 ms 59104 KB Output is correct
14 Correct 3745 ms 55716 KB Output is correct
15 Correct 3827 ms 55464 KB Output is correct
16 Correct 2062 ms 54016 KB Output is correct
17 Correct 3811 ms 55540 KB Output is correct
18 Correct 4344 ms 55208 KB Output is correct
19 Incorrect 3725 ms 58636 KB Output isn't correct
20 Halted 0 ms 0 KB -