oj.uz

Submission #38638

# Submission time Handle Problem Language Result Execution time Memory
38638 2018-01-05T08:40:43 Z alenam0161 Game (IOI13_game) C++14
100 / 100
 6976 ms 185152 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;
const int inf = 2e9;
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;
	int maxkey, minkey;
	node *l, *r;
	node(int _X = 0, ll valu = 0ll) {
		key = _X;
		val = valu;
		ans_tree = val;
		maxkey = minkey = key;
		prior = rand();
		l = r = NULL;
	}
};
inline 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));
		t->minkey = min(t->key, min(t->l ? t->l->minkey:inf,t->r ? t->r->minkey:inf));
		t->maxkey = max(t->key, max(t->l ? t->l->maxkey : -inf, t->r ? t->r->maxkey : -inf));
	}
}
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) {
	/* ... */
	srand(2781);
}
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;
	//printt(t);
	//cout << l << " <- || -> " << r << endl;
	if (t->maxkey<l || t->minkey>r)return 0ll;
	if (t->maxkey <= r && t->minkey >= l)return t->ans_tree;
	long long cur = gcd2(query_y(l, r, t->r), query_y(l, r, t->l));
	if (t->key >= l && t->key <= r)
		cur = gcd2(cur, t->val);
	return cur;
}
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 9 ms 142780 KB Output is correct
2 Correct 13 ms 142912 KB Output is correct
3 Correct 6 ms 142912 KB Output is correct
4 Correct 9 ms 142648 KB Output is correct
5 Correct 0 ms 142648 KB Output is correct
6 Correct 13 ms 142912 KB Output is correct
7 Correct 9 ms 142648 KB Output is correct
8 Correct 9 ms 142648 KB Output is correct
9 Correct 13 ms 142780 KB Output is correct
10 Correct 13 ms 142780 KB Output is correct
11 Correct 9 ms 142780 KB Output is correct
12 Correct 6 ms 142648 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 142780 KB Output is correct
2 Correct 6 ms 142648 KB Output is correct
3 Correct 3 ms 142648 KB Output is correct
4 Correct 1996 ms 162052 KB Output is correct
5 Correct 1333 ms 162052 KB Output is correct
6 Correct 2789 ms 162052 KB Output is correct
7 Correct 3003 ms 162052 KB Output is correct
8 Correct 1533 ms 152020 KB Output is correct
9 Correct 3266 ms 162052 KB Output is correct
10 Correct 2683 ms 162052 KB Output is correct
11 Correct 9 ms 142648 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 142780 KB Output is correct
2 Correct 9 ms 142912 KB Output is correct
3 Correct 6 ms 142912 KB Output is correct
4 Correct 3 ms 142648 KB Output is correct
5 Correct 0 ms 142648 KB Output is correct
6 Correct 9 ms 142912 KB Output is correct
7 Correct 9 ms 142648 KB Output is correct
8 Correct 0 ms 142648 KB Output is correct
9 Correct 9 ms 142780 KB Output is correct
10 Correct 9 ms 142780 KB Output is correct
11 Correct 6 ms 142780 KB Output is correct
12 Correct 1993 ms 162052 KB Output is correct
13 Correct 3699 ms 162052 KB Output is correct
14 Correct 646 ms 162052 KB Output is correct
15 Correct 3729 ms 162052 KB Output is correct
16 Correct 959 ms 162052 KB Output is correct
17 Correct 2043 ms 151888 KB Output is correct
18 Correct 4513 ms 162052 KB Output is correct
19 Correct 3886 ms 162052 KB Output is correct
20 Correct 3513 ms 162052 KB Output is correct
21 Correct 3 ms 142648 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 142780 KB Output is correct
2 Correct 9 ms 142912 KB Output is correct
3 Correct 3 ms 142912 KB Output is correct
4 Correct 0 ms 142648 KB Output is correct
5 Correct 0 ms 142648 KB Output is correct
6 Correct 6 ms 142912 KB Output is correct
7 Correct 6 ms 142648 KB Output is correct
8 Correct 9 ms 142648 KB Output is correct
9 Correct 13 ms 142780 KB Output is correct
10 Correct 9 ms 142780 KB Output is correct
11 Correct 6 ms 142780 KB Output is correct
12 Correct 2005 ms 162052 KB Output is correct
13 Correct 1276 ms 162052 KB Output is correct
14 Correct 3059 ms 162052 KB Output is correct
15 Correct 3283 ms 162052 KB Output is correct
16 Correct 1363 ms 152020 KB Output is correct
17 Correct 3036 ms 162052 KB Output is correct
18 Correct 2706 ms 162052 KB Output is correct
19 Correct 1739 ms 162052 KB Output is correct
20 Correct 3669 ms 162052 KB Output is correct
21 Correct 753 ms 162052 KB Output is correct
22 Correct 3813 ms 162052 KB Output is correct
23 Correct 953 ms 162052 KB Output is correct
24 Correct 2136 ms 151888 KB Output is correct
25 Correct 4593 ms 162052 KB Output is correct
26 Correct 3909 ms 162052 KB Output is correct
27 Correct 3516 ms 162052 KB Output is correct
28 Correct 893 ms 162052 KB Output is correct
29 Correct 2536 ms 162052 KB Output is correct
30 Correct 3959 ms 162052 KB Output is correct
31 Correct 3596 ms 162052 KB Output is correct
32 Correct 783 ms 162052 KB Output is correct
33 Correct 1022 ms 162052 KB Output is correct
34 Correct 679 ms 162052 KB Output is correct
35 Correct 2286 ms 152152 KB Output is correct
36 Correct 4696 ms 162052 KB Output is correct
37 Correct 3279 ms 162052 KB Output is correct
38 Correct 3439 ms 162052 KB Output is correct
39 Correct 3039 ms 157432 KB Output is correct
40 Correct 6 ms 142648 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 142780 KB Output is correct
2 Correct 16 ms 142912 KB Output is correct
3 Correct 13 ms 142912 KB Output is correct
4 Correct 6 ms 142648 KB Output is correct
5 Correct 0 ms 142648 KB Output is correct
6 Correct 9 ms 142912 KB Output is correct
7 Correct 6 ms 142648 KB Output is correct
8 Correct 0 ms 142648 KB Output is correct
9 Correct 16 ms 142780 KB Output is correct
10 Correct 6 ms 142780 KB Output is correct
11 Correct 16 ms 142780 KB Output is correct
12 Correct 2086 ms 162052 KB Output is correct
13 Correct 1189 ms 162052 KB Output is correct
14 Correct 3033 ms 162052 KB Output is correct
15 Correct 3236 ms 162052 KB Output is correct
16 Correct 1349 ms 152020 KB Output is correct
17 Correct 2893 ms 162052 KB Output is correct
18 Correct 2539 ms 162052 KB Output is correct
19 Correct 1939 ms 162052 KB Output is correct
20 Correct 3616 ms 162052 KB Output is correct
21 Correct 703 ms 162052 KB Output is correct
22 Correct 3606 ms 162052 KB Output is correct
23 Correct 956 ms 162052 KB Output is correct
24 Correct 2119 ms 151888 KB Output is correct
25 Correct 4529 ms 162052 KB Output is correct
26 Correct 3996 ms 162052 KB Output is correct
27 Correct 3693 ms 162052 KB Output is correct
28 Correct 873 ms 162052 KB Output is correct
29 Correct 2546 ms 162052 KB Output is correct
30 Correct 3643 ms 162052 KB Output is correct
31 Correct 3463 ms 162052 KB Output is correct
32 Correct 743 ms 162052 KB Output is correct
33 Correct 963 ms 162052 KB Output is correct
34 Correct 613 ms 162052 KB Output is correct
35 Correct 2116 ms 152152 KB Output is correct
36 Correct 4779 ms 162052 KB Output is correct
37 Correct 3443 ms 162052 KB Output is correct
38 Correct 3206 ms 162052 KB Output is correct
39 Correct 1179 ms 185152 KB Output is correct
40 Correct 4733 ms 185152 KB Output is correct
41 Correct 5733 ms 185152 KB Output is correct
42 Correct 5779 ms 185152 KB Output is correct
43 Correct 1596 ms 185152 KB Output is correct
44 Correct 1083 ms 185152 KB Output is correct
45 Correct 2669 ms 157432 KB Output is correct
46 Correct 6313 ms 185152 KB Output is correct
47 Correct 6976 ms 185152 KB Output is correct
48 Correct 6709 ms 185152 KB Output is correct
49 Correct 3 ms 142648 KB Output is correct