oj.uz

Submission #437309

# Submission time Handle Problem Language Result Execution time Memory
437309 2021-06-26T07:05:30 Z denverjin Game (IOI13_game) C++14
10 / 100
 13000 ms 6532 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long i64;

i64 gcd(i64 X, i64 Y) {
	i64 tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

struct Node {
	int x;
	i64 v, s;
	int sz;
	int ls, rs;
} t[22000 * 30];

const int null = 0;
int ndsz;

int new_node(int x, i64 v) {
	int i = ++ ndsz;
	t[i].x = x;
	t[i].v = t[i].s = v;
	t[i].sz = 1;
	t[i].ls = t[i].rs = null;
	return i;
}

void pushup(int x) {
	t[x].sz = t[t[x].ls].sz + 1 + t[t[x].rs].sz;
	t[x].s = gcd(t[t[x].ls].s, gcd(t[x].v, t[t[x].rs].s));
}

void split(int x, i64 v, int &a, int &b) {
	if (!x) return void(a = b = null);
	if (t[x].x <= v) a = x, split(t[x].rs, v, t[a].rs, b), pushup(a);
	else b = x, split(t[x].ls, v, a, t[b].ls), pushup(b);
}

std::mt19937 rng;

int rand(int l, int r) { return rng() % (r - l + 1) + l; }

int merge(int a, int b) {
	if (!a || !b) return a | b;
	if (rand(1, t[a].sz + t[b].sz) <= t[a].sz) return t[a].rs = merge(t[a].rs, b), pushup(a), a;
	else return t[b].ls = merge(a, t[b].ls), pushup(b), b;
}

void change(int &i, int p, i64 v) {
	int a, b, c;
	split(i, p, b, c);
	split(b, p - 1, a, b);
	if (!b) b = new_node(p, v);
	else t[b].v = t[b].s = v;
	i = merge(merge(a, b), c);
}

i64 query(int i, int l, int r) {
	if (i == null) return 0;
	i64 ans = 0;
	if (l <= t[i].x && t[i].x <= r) ans = gcd(ans, t[i].v);
	if (l < t[i].x && t[i].ls) ans = gcd(ans, query(t[i].ls, l, r));
	if (r > t[i].x && t[i].rs) ans = gcd(ans, query(t[i].rs, l, r));
	return ans;
}

struct SegNode {
	int nd;
	SegNode *ls, *rs;
};

void change(int x, int y, i64 v, SegNode *&i, int a, int b) {
	if (!i) i = new SegNode{0, nullptr, nullptr};
	if (a + 1 == b) return change(i->nd, y, v);
	int m = (a + b) >> 1;
	if (x < m) change(x, y, v, i->ls, a, m);
	else change(x, y, v, i->rs, m, b);
	change(i->nd, y, gcd(i->ls ? query(i->ls->nd, y, y) : 0, i->rs ? query(i->rs->nd, y, y) : 0));
}

i64 query(int l, int r, int L, int R, SegNode *i, int a, int b) {
	if (!i) return 0;
	if (l <= a && b <= r) return query(i->nd, L, R);
	if (r <= a || b <= l) return 0;
	int m = (a + b) >> 1;
	return gcd(query(l, r, L, R, i->ls, a, m), query(l, r, L, R, i->rs, m, b));
}

int R, C;
SegNode *rt;

void init(int _R, int _C) {
	R = _R; C = _C;
	rt = nullptr;
}

void update(int P, int Q, i64 K) {
	change(P, Q, K, rt, 0, R);
}

i64 calculate(int P, int Q, int U, int V) {
	return query(P, U + 1, Q, V, rt, 0, R);
}

#ifdef DEBUG
#include "grader.c"
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Execution timed out 13041 ms 4892 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13085 ms 6532 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13044 ms 4752 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13067 ms 4764 KB Time limit exceeded
13 Halted 0 ms 0 KB -