oj.uz

Submission #123968

# Submission time Handle Problem Language Result Execution time Memory
123968 2019-07-02T10:17:27 Z MAMBA Game (IOI13_game) C++17
37 / 100
 4297 ms 61208 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 48 ms 47864 KB Output is correct
2 Correct 49 ms 47992 KB Output is correct
3 Correct 49 ms 47992 KB Output is correct
4 Correct 46 ms 47864 KB Output is correct
5 Correct 46 ms 47836 KB Output is correct
6 Correct 49 ms 47996 KB Output is correct
7 Correct 48 ms 47836 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 47992 KB Output is correct
11 Correct 49 ms 47992 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 47992 KB Output is correct
3 Correct 46 ms 47864 KB Output is correct
4 Correct 3456 ms 61048 KB Output is correct
5 Correct 3156 ms 60928 KB Output is correct
6 Correct 3770 ms 58416 KB Output is correct
7 Correct 3821 ms 57868 KB Output is correct
8 Correct 1992 ms 56184 KB Output is correct
9 Correct 3812 ms 58044 KB Output is correct
10 Correct 4294 ms 57628 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 46 ms 47916 KB Output is correct
2 Correct 48 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 55 ms 47864 KB Output is correct
6 Correct 48 ms 47864 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 45 ms 47992 KB Output is correct
9 Correct 47 ms 47964 KB Output is correct
10 Correct 46 ms 47864 KB Output is correct
11 Correct 54 ms 47864 KB Output is correct
12 Incorrect 3714 ms 60656 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 47864 KB Output is correct
2 Correct 48 ms 47992 KB Output is correct
3 Correct 49 ms 47964 KB Output is correct
4 Correct 45 ms 47992 KB Output is correct
5 Correct 54 ms 47864 KB Output is correct
6 Correct 49 ms 47992 KB Output is correct
7 Correct 53 ms 47992 KB Output is correct
8 Correct 55 ms 47868 KB Output is correct
9 Correct 47 ms 47996 KB Output is correct
10 Correct 46 ms 47992 KB Output is correct
11 Correct 47 ms 47992 KB Output is correct
12 Correct 3471 ms 61208 KB Output is correct
13 Correct 3201 ms 60924 KB Output is correct
14 Correct 3743 ms 58264 KB Output is correct
15 Correct 3800 ms 57840 KB Output is correct
16 Correct 2007 ms 56096 KB Output is correct
17 Correct 3774 ms 57964 KB Output is correct
18 Correct 4286 ms 57684 KB Output is correct
19 Incorrect 3700 ms 60660 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 55 ms 47856 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 45 ms 47836 KB Output is correct
5 Correct 46 ms 47864 KB Output is correct
6 Correct 51 ms 47968 KB Output is correct
7 Correct 46 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 47 ms 47992 KB Output is correct
10 Correct 46 ms 47864 KB Output is correct
11 Correct 46 ms 47884 KB Output is correct
12 Correct 3432 ms 61144 KB Output is correct
13 Correct 3166 ms 60912 KB Output is correct
14 Correct 3770 ms 58348 KB Output is correct
15 Correct 3812 ms 57888 KB Output is correct
16 Correct 2003 ms 56284 KB Output is correct
17 Correct 3798 ms 58008 KB Output is correct
18 Correct 4297 ms 57576 KB Output is correct
19 Incorrect 3729 ms 60652 KB Output isn't correct
20 Halted 0 ms 0 KB -