oj.uz

Submission #123926

# Submission time Handle Problem Language Result Execution time Memory
123926 2019-07-02T09:46:52 Z MAMBA Game (IOI13_game) C++17
37 / 100
 3117 ms 21756 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 = 16;

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 10 ms 10104 KB Output is correct
2 Correct 13 ms 10104 KB Output is correct
3 Correct 14 ms 10232 KB Output is correct
4 Correct 11 ms 10104 KB Output is correct
5 Correct 11 ms 10104 KB Output is correct
6 Correct 13 ms 10232 KB Output is correct
7 Correct 10 ms 10232 KB Output is correct
8 Correct 10 ms 10104 KB Output is correct
9 Correct 12 ms 10232 KB Output is correct
10 Correct 11 ms 10232 KB Output is correct
11 Correct 11 ms 10232 KB Output is correct
12 Correct 10 ms 10104 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10104 KB Output is correct
2 Correct 10 ms 10104 KB Output is correct
3 Correct 10 ms 10104 KB Output is correct
4 Correct 2481 ms 17316 KB Output is correct
5 Correct 2203 ms 21596 KB Output is correct
6 Correct 2638 ms 18840 KB Output is correct
7 Correct 2745 ms 18684 KB Output is correct
8 Correct 1411 ms 17876 KB Output is correct
9 Correct 2682 ms 18892 KB Output is correct
10 Correct 3117 ms 18372 KB Output is correct
11 Correct 14 ms 10104 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10108 KB Output is correct
2 Correct 13 ms 10236 KB Output is correct
3 Correct 17 ms 10232 KB Output is correct
4 Correct 10 ms 10104 KB Output is correct
5 Correct 13 ms 10104 KB Output is correct
6 Correct 13 ms 10104 KB Output is correct
7 Correct 10 ms 10104 KB Output is correct
8 Correct 13 ms 10220 KB Output is correct
9 Correct 14 ms 10260 KB Output is correct
10 Correct 13 ms 10104 KB Output is correct
11 Correct 11 ms 10104 KB Output is correct
12 Incorrect 2750 ms 21420 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10104 KB Output is correct
2 Correct 13 ms 10232 KB Output is correct
3 Correct 13 ms 10232 KB Output is correct
4 Correct 10 ms 10104 KB Output is correct
5 Correct 11 ms 10104 KB Output is correct
6 Correct 12 ms 10232 KB Output is correct
7 Correct 10 ms 10104 KB Output is correct
8 Correct 10 ms 10104 KB Output is correct
9 Correct 12 ms 10104 KB Output is correct
10 Correct 12 ms 10232 KB Output is correct
11 Correct 13 ms 10104 KB Output is correct
12 Correct 2517 ms 21584 KB Output is correct
13 Correct 2197 ms 21444 KB Output is correct
14 Correct 2626 ms 18976 KB Output is correct
15 Correct 2710 ms 18652 KB Output is correct
16 Correct 1405 ms 17940 KB Output is correct
17 Correct 2680 ms 18852 KB Output is correct
18 Correct 3103 ms 18436 KB Output is correct
19 Incorrect 2742 ms 21504 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10104 KB Output is correct
2 Correct 13 ms 10232 KB Output is correct
3 Correct 14 ms 10232 KB Output is correct
4 Correct 10 ms 10104 KB Output is correct
5 Correct 10 ms 10104 KB Output is correct
6 Correct 13 ms 10216 KB Output is correct
7 Correct 10 ms 10104 KB Output is correct
8 Correct 10 ms 10104 KB Output is correct
9 Correct 12 ms 10232 KB Output is correct
10 Correct 11 ms 10204 KB Output is correct
11 Correct 11 ms 10232 KB Output is correct
12 Correct 2464 ms 21748 KB Output is correct
13 Correct 2188 ms 21756 KB Output is correct
14 Correct 2621 ms 19084 KB Output is correct
15 Correct 2709 ms 18608 KB Output is correct
16 Correct 1426 ms 17784 KB Output is correct
17 Correct 2704 ms 18876 KB Output is correct
18 Correct 3080 ms 18456 KB Output is correct
19 Incorrect 2762 ms 21384 KB Output isn't correct
20 Halted 0 ms 0 KB -