oj.uz

Submission #123948

# Submission time Handle Problem Language Result Execution time Memory
123948 2019-07-02T10:00:11 Z MAMBA Game (IOI13_game) C++17
10 / 100
 13000 ms 53664 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 * 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 && false) {
		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 46 ms 47864 KB Output is correct
2 Correct 48 ms 47964 KB Output is correct
3 Correct 47 ms 47964 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 47932 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 47 ms 47960 KB Output is correct
10 Correct 46 ms 47864 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Correct 45 ms 47864 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 45 ms 47956 KB Output is correct
3 Correct 45 ms 47836 KB Output is correct
4 Execution timed out 13083 ms 53512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 47 ms 47996 KB Output is correct
3 Correct 49 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 47964 KB Output is correct
7 Correct 45 ms 47992 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 45 ms 47992 KB Output is correct
10 Correct 46 ms 47864 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Execution timed out 13106 ms 53264 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47892 KB Output is correct
2 Correct 48 ms 48008 KB Output is correct
3 Correct 48 ms 47956 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 44 ms 47892 KB Output is correct
8 Correct 45 ms 47864 KB Output is correct
9 Correct 46 ms 47964 KB Output is correct
10 Correct 45 ms 47956 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Execution timed out 13013 ms 53480 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 47 ms 47992 KB Output is correct
3 Correct 48 ms 47924 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 44 ms 47864 KB Output is correct
6 Correct 48 ms 47864 KB Output is correct
7 Correct 53 ms 47864 KB Output is correct
8 Correct 53 ms 47864 KB Output is correct
9 Correct 54 ms 47864 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 50 ms 47864 KB Output is correct
12 Execution timed out 13039 ms 53664 KB Time limit exceeded
13 Halted 0 ms 0 KB -