oj.uz

Submission #123979

# Submission time Handle Problem Language Result Execution time Memory
123979 2019-07-02T10:24:20 Z MAMBA Game (IOI13_game) C++17
37 / 100
 4283 ms 61004 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 + 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 44 ms 47864 KB Output is correct
2 Correct 47 ms 47864 KB Output is correct
3 Correct 47 ms 47992 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 47 ms 47964 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 45 ms 47868 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 48036 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47964 KB Output is correct
2 Correct 44 ms 47868 KB Output is correct
3 Correct 44 ms 47864 KB Output is correct
4 Correct 3436 ms 61004 KB Output is correct
5 Correct 3217 ms 60912 KB Output is correct
6 Correct 3729 ms 58336 KB Output is correct
7 Correct 3802 ms 57732 KB Output is correct
8 Correct 2004 ms 56092 KB Output is correct
9 Correct 3786 ms 58056 KB Output is correct
10 Correct 4265 ms 57488 KB Output is correct
11 Correct 43 ms 47864 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47852 KB Output is correct
2 Correct 47 ms 47984 KB Output is correct
3 Correct 48 ms 47936 KB Output is correct
4 Correct 44 ms 47796 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 47 ms 47868 KB Output is correct
7 Correct 45 ms 47904 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 47952 KB Output is correct
11 Correct 45 ms 47868 KB Output is correct
12 Incorrect 3738 ms 60680 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 47 ms 47864 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 45 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 44 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 47992 KB Output is correct
12 Correct 3479 ms 60852 KB Output is correct
13 Correct 3148 ms 60848 KB Output is correct
14 Correct 3737 ms 58180 KB Output is correct
15 Correct 3784 ms 57776 KB Output is correct
16 Correct 1987 ms 53752 KB Output is correct
17 Correct 3819 ms 54836 KB Output is correct
18 Correct 4281 ms 53596 KB Output is correct
19 Incorrect 3704 ms 57108 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47956 KB Output is correct
2 Correct 46 ms 48000 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 52 ms 47864 KB Output is correct
5 Correct 44 ms 47992 KB Output is correct
6 Correct 47 ms 47996 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 45 ms 47964 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 45 ms 47992 KB Output is correct
12 Correct 3420 ms 57320 KB Output is correct
13 Correct 3147 ms 57600 KB Output is correct
14 Correct 3738 ms 54008 KB Output is correct
15 Correct 3812 ms 53784 KB Output is correct
16 Correct 1994 ms 52440 KB Output is correct
17 Correct 3784 ms 53780 KB Output is correct
18 Correct 4283 ms 53372 KB Output is correct
19 Incorrect 3713 ms 57084 KB Output isn't correct
20 Halted 0 ms 0 KB -