oj.uz

Submission #123951

# Submission time Handle Problem Language Result Execution time Memory
123951 2019-07-02T10:04:27 Z MAMBA Game (IOI13_game) C++17
37 / 100
 4273 ms 57024 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 45 ms 47992 KB Output is correct
2 Correct 47 ms 48000 KB Output is correct
3 Correct 48 ms 47992 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 46 ms 47992 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47952 KB Output is correct
9 Correct 46 ms 47992 KB Output is correct
10 Correct 44 ms 47992 KB Output is correct
11 Correct 45 ms 47864 KB Output is correct
12 Correct 44 ms 47864 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 47864 KB Output is correct
3 Correct 44 ms 47864 KB Output is correct
4 Correct 3445 ms 56776 KB Output is correct
5 Correct 3140 ms 56920 KB Output is correct
6 Correct 3787 ms 53664 KB Output is correct
7 Correct 3781 ms 53536 KB Output is correct
8 Correct 2099 ms 51956 KB Output is correct
9 Correct 3807 ms 53456 KB Output is correct
10 Correct 4257 ms 53108 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 47948 KB Output is correct
2 Correct 47 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 44 ms 47896 KB Output is correct
6 Correct 46 ms 47864 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 43 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 45 ms 47940 KB Output is correct
12 Incorrect 3702 ms 56416 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 46 ms 47964 KB Output is correct
3 Correct 48 ms 47992 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 45 ms 47828 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 44 ms 48032 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 47964 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 3447 ms 56768 KB Output is correct
13 Correct 3163 ms 57024 KB Output is correct
14 Correct 3729 ms 53696 KB Output is correct
15 Correct 3834 ms 53108 KB Output is correct
16 Correct 2007 ms 51904 KB Output is correct
17 Correct 3815 ms 53332 KB Output is correct
18 Correct 4273 ms 52984 KB Output is correct
19 Incorrect 3714 ms 56588 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 47952 KB Output is correct
2 Correct 47 ms 47932 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 46 ms 47992 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47980 KB Output is correct
10 Correct 46 ms 47868 KB Output is correct
11 Correct 46 ms 47836 KB Output is correct
12 Correct 3445 ms 56612 KB Output is correct
13 Correct 3146 ms 56852 KB Output is correct
14 Correct 3750 ms 53784 KB Output is correct
15 Correct 3784 ms 53456 KB Output is correct
16 Correct 1989 ms 51960 KB Output is correct
17 Correct 3781 ms 53332 KB Output is correct
18 Correct 4269 ms 53076 KB Output is correct
19 Incorrect 3733 ms 56488 KB Output isn't correct
20 Halted 0 ms 0 KB -