oj.uz

Submission #123950

# Submission time Handle Problem Language Result Execution time Memory
123950 2019-07-02T10:02:58 Z MAMBA Game (IOI13_game) C++17
10 / 100
 13000 ms 54960 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 = 2000;
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 48 ms 47992 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 47864 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 46 ms 47936 KB Output is correct
10 Correct 45 ms 47992 KB Output is correct
11 Correct 45 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 44 ms 47992 KB Output is correct
2 Correct 45 ms 47864 KB Output is correct
3 Correct 44 ms 47864 KB Output is correct
4 Execution timed out 13054 ms 54768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47864 KB Output is correct
2 Correct 46 ms 47880 KB Output is correct
3 Correct 47 ms 47864 KB Output is correct
4 Correct 45 ms 47864 KB Output is correct
5 Correct 43 ms 47864 KB Output is correct
6 Correct 47 ms 47992 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 45 ms 47928 KB Output is correct
10 Correct 51 ms 48024 KB Output is correct
11 Correct 46 ms 47964 KB Output is correct
12 Execution timed out 13101 ms 54876 KB Time limit exceeded
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 47944 KB Output is correct
3 Correct 48 ms 47864 KB Output is correct
4 Correct 44 ms 47864 KB Output is correct
5 Correct 45 ms 47840 KB Output is correct
6 Correct 47 ms 47864 KB Output is correct
7 Correct 44 ms 47864 KB Output is correct
8 Correct 44 ms 47864 KB Output is correct
9 Correct 63 ms 47864 KB Output is correct
10 Correct 50 ms 47896 KB Output is correct
11 Correct 46 ms 47864 KB Output is correct
12 Execution timed out 13104 ms 54960 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 47 ms 47864 KB Output is correct
4 Correct 45 ms 47868 KB Output is correct
5 Correct 45 ms 47864 KB Output is correct
6 Correct 48 ms 47848 KB Output is correct
7 Correct 45 ms 47868 KB Output is correct
8 Correct 44 ms 47808 KB Output is correct
9 Correct 55 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 13069 ms 54960 KB Time limit exceeded
13 Halted 0 ms 0 KB -