oj.uz

Submission #123971

# Submission time Handle Problem Language Result Execution time Memory
123971 2019-07-02T10:19:12 Z MAMBA Game (IOI13_game) C++17
37 / 100
 4280 ms 61016 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) {
      assert(r >= l);
		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 43 ms 47864 KB Output is correct
2 Correct 46 ms 47864 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 44 ms 47908 KB Output is correct
6 Correct 46 ms 47864 KB Output is correct
7 Correct 43 ms 47864 KB Output is correct
8 Correct 43 ms 47860 KB Output is correct
9 Correct 45 ms 47992 KB Output is correct
10 Correct 45 ms 47868 KB Output is correct
11 Correct 44 ms 47916 KB Output is correct
12 Correct 44 ms 47924 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 47828 KB Output is correct
3 Correct 44 ms 47864 KB Output is correct
4 Correct 3428 ms 56604 KB Output is correct
5 Correct 3139 ms 56872 KB Output is correct
6 Correct 3732 ms 53724 KB Output is correct
7 Correct 3779 ms 53348 KB Output is correct
8 Correct 1985 ms 52020 KB Output is correct
9 Correct 3790 ms 53328 KB Output is correct
10 Correct 4270 ms 52892 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 44 ms 47892 KB Output is correct
2 Correct 47 ms 47948 KB Output is correct
3 Correct 48 ms 47992 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 45 ms 47864 KB Output is correct
6 Correct 47 ms 47964 KB Output is correct
7 Correct 45 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 46 ms 47996 KB Output is correct
10 Correct 45 ms 47936 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Incorrect 3714 ms 56524 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 47 ms 47992 KB Output is correct
3 Correct 52 ms 47992 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 44 ms 47992 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 44 ms 47868 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 45 ms 47864 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 50 ms 47992 KB Output is correct
12 Correct 3428 ms 56748 KB Output is correct
13 Correct 3133 ms 56860 KB Output is correct
14 Correct 3745 ms 54160 KB Output is correct
15 Correct 3820 ms 56160 KB Output is correct
16 Correct 2001 ms 56084 KB Output is correct
17 Correct 3789 ms 58004 KB Output is correct
18 Correct 4280 ms 57520 KB Output is correct
19 Incorrect 3696 ms 60540 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 47836 KB Output is correct
2 Correct 47 ms 47964 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 45 ms 47864 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 45 ms 48052 KB Output is correct
8 Correct 46 ms 47912 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 45 ms 47956 KB Output is correct
11 Correct 46 ms 47880 KB Output is correct
12 Correct 3426 ms 61016 KB Output is correct
13 Correct 3192 ms 60788 KB Output is correct
14 Correct 3743 ms 58176 KB Output is correct
15 Correct 3789 ms 57744 KB Output is correct
16 Correct 1997 ms 56016 KB Output is correct
17 Correct 3786 ms 58024 KB Output is correct
18 Correct 4269 ms 57492 KB Output is correct
19 Incorrect 3691 ms 60560 KB Output isn't correct
20 Halted 0 ms 0 KB -