oj.uz

Submission #123928

# Submission time Handle Problem Language Result Execution time Memory
123928 2019-07-02T09:49:50 Z MAMBA Game (IOI13_game) C++17
37 / 100
 3246 ms 21236 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 = 200;
const int N = 22010;

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) {}

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 12 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 16 ms 12284 KB Output is correct
4 Correct 12 ms 12152 KB Output is correct
5 Correct 12 ms 12152 KB Output is correct
6 Correct 14 ms 12308 KB Output is correct
7 Correct 12 ms 12152 KB Output is correct
8 Correct 12 ms 12152 KB Output is correct
9 Correct 13 ms 12280 KB Output is correct
10 Correct 13 ms 12284 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Correct 12 ms 12280 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct
3 Correct 12 ms 12280 KB Output is correct
4 Correct 2598 ms 20636 KB Output is correct
5 Correct 2332 ms 20980 KB Output is correct
6 Correct 2805 ms 17884 KB Output is correct
7 Correct 2857 ms 17528 KB Output is correct
8 Correct 1477 ms 16920 KB Output is correct
9 Correct 2855 ms 17728 KB Output is correct
10 Correct 3229 ms 17280 KB Output is correct
11 Correct 12 ms 12280 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12156 KB Output is correct
2 Correct 15 ms 12280 KB Output is correct
3 Correct 16 ms 12280 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 12 ms 12280 KB Output is correct
6 Correct 15 ms 12252 KB Output is correct
7 Correct 12 ms 12252 KB Output is correct
8 Correct 12 ms 12280 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 14 ms 12292 KB Output is correct
11 Correct 14 ms 12280 KB Output is correct
12 Incorrect 2909 ms 20920 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12280 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 15 ms 12284 KB Output is correct
4 Correct 12 ms 12280 KB Output is correct
5 Correct 12 ms 12244 KB Output is correct
6 Correct 14 ms 12280 KB Output is correct
7 Correct 12 ms 12280 KB Output is correct
8 Correct 12 ms 12280 KB Output is correct
9 Correct 13 ms 12280 KB Output is correct
10 Correct 13 ms 12280 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Correct 2609 ms 20836 KB Output is correct
13 Correct 2335 ms 21108 KB Output is correct
14 Correct 2788 ms 17824 KB Output is correct
15 Correct 2867 ms 17648 KB Output is correct
16 Correct 1481 ms 16776 KB Output is correct
17 Correct 2839 ms 17780 KB Output is correct
18 Correct 3246 ms 17380 KB Output is correct
19 Incorrect 2900 ms 20808 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 15 ms 12284 KB Output is correct
3 Correct 16 ms 12304 KB Output is correct
4 Correct 15 ms 12152 KB Output is correct
5 Correct 16 ms 12280 KB Output is correct
6 Correct 15 ms 12280 KB Output is correct
7 Correct 12 ms 12152 KB Output is correct
8 Correct 12 ms 12152 KB Output is correct
9 Correct 13 ms 12288 KB Output is correct
10 Correct 13 ms 12280 KB Output is correct
11 Correct 13 ms 12280 KB Output is correct
12 Correct 2630 ms 20936 KB Output is correct
13 Correct 2331 ms 21236 KB Output is correct
14 Correct 2769 ms 17824 KB Output is correct
15 Correct 2856 ms 17496 KB Output is correct
16 Correct 1482 ms 16860 KB Output is correct
17 Correct 2819 ms 17812 KB Output is correct
18 Correct 3226 ms 17368 KB Output is correct
19 Incorrect 2908 ms 20876 KB Output isn't correct
20 Halted 0 ms 0 KB -