oj.uz

Submission #38628

# Submission time Handle Problem Language Result Execution time Memory
38628 2018-01-05T07:06:14 Z alenam0161 Game (IOI13_game) C++14
80 / 100
 13000 ms 141544 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include "game.h"

#define  pn node*
#define  ps segtree*
using namespace std;
const int N = 1e9;
typedef long long ll;
long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

struct node {
	ll val;
	int key;//index 
	int prior;
	ll ans_tree;
	node *l, *r;
	node(int _X = 0, ll valu = 0ll) {
		key = _X;
		val = valu;
		ans_tree = val;
		prior = rand();
		l = r = NULL;
	}
}; 
void upd_ans(pn &t) {
	if (t) {
		t->ans_tree = gcd2(t->val,
			gcd2(t->l ? t->l->ans_tree : 0ll, t->r ? t->r->ans_tree : 0ll)
		);
	}
}
void split(pn t, pn &l, pn &r, int key) {
	if (!t) {
		l = r = NULL; return;
	}
	if (t->key > key) {
		split(t->l, l, t->l, key); r = t;
	}
	else {
		split(t->r, t->r, r, key); l = t;
	}
	upd_ans(l);
	upd_ans(r);
}
void merge(pn &t, pn l, pn r) {
	if (!l || !r) {
		t = l ? l : r;
	}
	else {
		if (l->prior > r->prior) {
			merge(l->r, l->r, r); t = l;
		}
		else {
			merge(r->l, l, r->l); t = r;
		}
	}
	upd_ans(t);
}
void insert(pn &t, pn it) {
	if (!t) {
		t = it;
	}
	else {
		if (t->prior < it->prior) {
			split(t, it->l, it->r, it->key); t = it;
		}
		else{
			if (t->key > it->key) {
				insert(t->l, it);
			}
			else insert(t->r, it);
		}
	}
	upd_ans(t);
}
void erase(pn &t, int key) {
	if (!t)return;
	if (t->key == key) {
		merge(t, t->l, t->r);
	}
	else {
		if (t->key > key)erase(t->l, key);
		else erase(t->r, key);
	}
	upd_ans(t);
}
struct segtree {
	node *down;
	segtree *l, *r;
	segtree(node *U = NULL) {
		down = U;
		l = r = NULL;
	}
};
ps root;
ps next_sg() {
	static segtree SEG[2000 * 1000];
	static int c1 = 0;
	return &SEG[c1++];
}
pn next_node() {
	static node an[2000 * 1000];
	static int c2 = 0;
	return &an[c2++];
}
void init(int R, int C) {
	/* ... */
}
void printt(pn t, int lv = 0) {
	if (!t)return;
	printt(t->l, lv + 1);
	cout <<" LEVEL "<<lv<<" "<< t->val << " " << t->ans_tree << " " << t->key << " " << t->prior << endl;
	printt(t->r, lv + 1);
}
ll get_ans(pn t, int key) {
	if (!t)return 0ll;
	if (t->key == key)return t->val;
	else {
		if (t->key > key) {
			return get_ans(t->l, key);
		}
		else return get_ans(t->r, key);
	}
}
void update_sg(int x, int y, long long vl, ps& t, int l, int r) {
	if (!t) {
		t = next_sg();
	}
	if (l == r) {
		erase(t->down, y);
		pn cur = new node(y, vl);
		insert(t->down, cur);
	}
	else {
		int m = (l + r) / 2;
		if (x <= m)update_sg(x, y, vl, t->l, l, m);
		else update_sg(x, y, vl, t->r, m + 1, r);
		ll a1 = t->l ? get_ans(t->l->down, y):0ll;
		ll a2 = t->r ? get_ans(t->r->down, y):0ll;
		erase(t->down, y);
		pn cur = new node(y, gcd2(a1,a2));
		insert(t->down, cur);
	}
}
void update(int P, int Q, long long K) {
	update_sg(P, Q, K,root, 0, N);
}
long long query_y(int l, int r, pn t) {
	if (!t)return 0ll;
	pn tl; pn tr;
	split(t, tl, t, l - 1);
	split(t, t, tr, r);
	long long ans = t ? t->ans_tree:0ll;
	merge(t, tl, t);
	merge(t, t, tr);
	return ans;
}
long long query_x(int xx, int xy, int yx, int yy, ps t, int l, int r) {
	if (!t)return 0ll;
	if (xx <= l&&r <= xy) {
		return query_y(yx, yy, t->down);
	}
	else {
		int m = (l + r) / 2;
		long long cur = 0;
		if (xx <= m)cur = gcd2(cur,query_x(xx, xy, yx, yy, t->l, l, m));
		if (xy> m)cur = gcd2(cur, query_x(xx, xy, yx, yy, t->r, m+1, r));
		return cur;
	}
}
long long calculate(int P, int Q, int U, int V) {
	return query_x(P,U,Q,V,root,0,N);
}

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 6 ms 127156 KB Output is correct
2 Correct 16 ms 127156 KB Output is correct
3 Correct 13 ms 127156 KB Output is correct
4 Correct 9 ms 127024 KB Output is correct
5 Correct 0 ms 127024 KB Output is correct
6 Correct 13 ms 127156 KB Output is correct
7 Correct 0 ms 127024 KB Output is correct
8 Correct 3 ms 127024 KB Output is correct
9 Correct 9 ms 127156 KB Output is correct
10 Correct 13 ms 127024 KB Output is correct
11 Correct 6 ms 127156 KB Output is correct
12 Correct 9 ms 127024 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127156 KB Output is correct
2 Correct 9 ms 127024 KB Output is correct
3 Correct 3 ms 127024 KB Output is correct
4 Correct 2623 ms 141544 KB Output is correct
5 Correct 1396 ms 141544 KB Output is correct
6 Correct 5483 ms 141544 KB Output is correct
7 Correct 5916 ms 141544 KB Output is correct
8 Correct 3429 ms 134020 KB Output is correct
9 Correct 5916 ms 141544 KB Output is correct
10 Correct 4626 ms 141544 KB Output is correct
11 Correct 3 ms 127024 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 127156 KB Output is correct
2 Correct 13 ms 127156 KB Output is correct
3 Correct 13 ms 127156 KB Output is correct
4 Correct 3 ms 127024 KB Output is correct
5 Correct 0 ms 127024 KB Output is correct
6 Correct 13 ms 127156 KB Output is correct
7 Correct 3 ms 127024 KB Output is correct
8 Correct 6 ms 127024 KB Output is correct
9 Correct 6 ms 127156 KB Output is correct
10 Correct 3 ms 127024 KB Output is correct
11 Correct 9 ms 127156 KB Output is correct
12 Correct 2769 ms 141544 KB Output is correct
13 Correct 8599 ms 141544 KB Output is correct
14 Correct 1176 ms 141544 KB Output is correct
15 Correct 9023 ms 141544 KB Output is correct
16 Correct 1713 ms 141544 KB Output is correct
17 Correct 6516 ms 134020 KB Output is correct
18 Correct 12663 ms 141544 KB Output is correct
19 Correct 9959 ms 141544 KB Output is correct
20 Correct 9943 ms 141544 KB Output is correct
21 Correct 0 ms 127024 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 127156 KB Output is correct
2 Correct 26 ms 127156 KB Output is correct
3 Correct 6 ms 127156 KB Output is correct
4 Correct 9 ms 127024 KB Output is correct
5 Correct 0 ms 127024 KB Output is correct
6 Correct 6 ms 127156 KB Output is correct
7 Correct 3 ms 127024 KB Output is correct
8 Correct 0 ms 127024 KB Output is correct
9 Correct 6 ms 127156 KB Output is correct
10 Correct 3 ms 127024 KB Output is correct
11 Correct 3 ms 127156 KB Output is correct
12 Correct 2713 ms 141544 KB Output is correct
13 Correct 1423 ms 141544 KB Output is correct
14 Correct 5459 ms 141544 KB Output is correct
15 Correct 5989 ms 141544 KB Output is correct
16 Correct 3606 ms 134020 KB Output is correct
17 Correct 6216 ms 141544 KB Output is correct
18 Correct 4956 ms 141544 KB Output is correct
19 Correct 2673 ms 141544 KB Output is correct
20 Correct 8769 ms 141544 KB Output is correct
21 Correct 1206 ms 141544 KB Output is correct
22 Correct 9359 ms 141544 KB Output is correct
23 Correct 1753 ms 141544 KB Output is correct
24 Correct 6999 ms 134020 KB Output is correct
25 Correct 12073 ms 141544 KB Output is correct
26 Correct 10333 ms 141544 KB Output is correct
27 Correct 9993 ms 141544 KB Output is correct
28 Correct 2643 ms 141544 KB Output is correct
29 Correct 3709 ms 141544 KB Output is correct
30 Correct 12086 ms 141544 KB Output is correct
31 Correct 10936 ms 141544 KB Output is correct
32 Correct 1339 ms 141544 KB Output is correct
33 Correct 2373 ms 141544 KB Output is correct
34 Correct 3069 ms 141544 KB Output is correct
35 Correct 6853 ms 134152 KB Output is correct
36 Correct 12399 ms 141544 KB Output is correct
37 Correct 9823 ms 141544 KB Output is correct
38 Correct 11239 ms 141544 KB Output is correct
39 Correct 8286 ms 138112 KB Output is correct
40 Correct 6 ms 127024 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 127156 KB Output is correct
2 Correct 9 ms 127156 KB Output is correct
3 Correct 13 ms 127156 KB Output is correct
4 Correct 0 ms 127024 KB Output is correct
5 Correct 0 ms 127024 KB Output is correct
6 Correct 9 ms 127156 KB Output is correct
7 Correct 9 ms 127024 KB Output is correct
8 Correct 9 ms 127024 KB Output is correct
9 Correct 13 ms 127156 KB Output is correct
10 Correct 6 ms 127024 KB Output is correct
11 Correct 3 ms 127156 KB Output is correct
12 Correct 2796 ms 141544 KB Output is correct
13 Correct 1573 ms 141544 KB Output is correct
14 Correct 5326 ms 141544 KB Output is correct
15 Correct 5939 ms 141544 KB Output is correct
16 Correct 3489 ms 134020 KB Output is correct
17 Correct 5936 ms 141544 KB Output is correct
18 Correct 5069 ms 141544 KB Output is correct
19 Correct 2563 ms 141544 KB Output is correct
20 Correct 8643 ms 141544 KB Output is correct
21 Correct 1269 ms 141544 KB Output is correct
22 Correct 9209 ms 141544 KB Output is correct
23 Correct 1716 ms 141544 KB Output is correct
24 Correct 6859 ms 134020 KB Output is correct
25 Execution timed out 13000 ms 141544 KB Execution timed out
26 Halted 0 ms 0 KB -