oj.uz

Submission #38637

# Submission time Handle Problem Language Result Execution time Memory
38637 2018-01-05T07:56:19 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;
	}
}; 
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));
	}
}
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;
	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 0 ms 127156 KB Output is correct
2 Correct 13 ms 127156 KB Output is correct
3 Correct 6 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 9 ms 127156 KB Output is correct
7 Correct 6 ms 127024 KB Output is correct
8 Correct 6 ms 127024 KB Output is correct
9 Correct 9 ms 127156 KB Output is correct
10 Correct 0 ms 127024 KB Output is correct
11 Correct 13 ms 127156 KB Output is correct
12 Correct 6 ms 127024 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 127156 KB Output is correct
2 Correct 0 ms 127024 KB Output is correct
3 Correct 6 ms 127024 KB Output is correct
4 Correct 2569 ms 141544 KB Output is correct
5 Correct 1329 ms 141544 KB Output is correct
6 Correct 5309 ms 141544 KB Output is correct
7 Correct 5816 ms 141544 KB Output is correct
8 Correct 3486 ms 134020 KB Output is correct
9 Correct 5586 ms 141544 KB Output is correct
10 Correct 4806 ms 141544 KB Output is correct
11 Correct 9 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 9 ms 127156 KB Output is correct
3 Correct 9 ms 127156 KB Output is correct
4 Correct 6 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 6 ms 127024 KB Output is correct
8 Correct 9 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 2659 ms 141544 KB Output is correct
13 Correct 8393 ms 141544 KB Output is correct
14 Correct 1179 ms 141544 KB Output is correct
15 Correct 8739 ms 141544 KB Output is correct
16 Correct 1583 ms 141544 KB Output is correct
17 Correct 6339 ms 134020 KB Output is correct
18 Correct 12286 ms 141544 KB Output is correct
19 Correct 9836 ms 141544 KB Output is correct
20 Correct 9909 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 13 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 3 ms 127024 KB Output is correct
5 Correct 0 ms 127024 KB Output is correct
6 Correct 16 ms 127156 KB Output is correct
7 Correct 9 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 16 ms 127024 KB Output is correct
11 Correct 6 ms 127156 KB Output is correct
12 Correct 2323 ms 141544 KB Output is correct
13 Correct 1343 ms 141544 KB Output is correct
14 Correct 5283 ms 141544 KB Output is correct
15 Correct 5593 ms 141544 KB Output is correct
16 Correct 3389 ms 134020 KB Output is correct
17 Correct 5969 ms 141544 KB Output is correct
18 Correct 4703 ms 141544 KB Output is correct
19 Correct 2483 ms 141544 KB Output is correct
20 Correct 8169 ms 141544 KB Output is correct
21 Correct 1153 ms 141544 KB Output is correct
22 Correct 8473 ms 141544 KB Output is correct
23 Correct 1599 ms 141544 KB Output is correct
24 Correct 6503 ms 134020 KB Output is correct
25 Correct 12209 ms 141544 KB Output is correct
26 Correct 9939 ms 141544 KB Output is correct
27 Correct 9603 ms 141544 KB Output is correct
28 Correct 2756 ms 141544 KB Output is correct
29 Correct 3513 ms 141544 KB Output is correct
30 Correct 11156 ms 141544 KB Output is correct
31 Correct 10346 ms 141544 KB Output is correct
32 Correct 1299 ms 141544 KB Output is correct
33 Correct 2423 ms 141544 KB Output is correct
34 Correct 3026 ms 141544 KB Output is correct
35 Correct 6986 ms 134152 KB Output is correct
36 Correct 12723 ms 141544 KB Output is correct
37 Correct 10439 ms 141544 KB Output is correct
38 Correct 10766 ms 141544 KB Output is correct
39 Correct 9016 ms 138112 KB Output is correct
40 Correct 3 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 9 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 0 ms 127024 KB Output is correct
8 Correct 3 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 0 ms 127156 KB Output is correct
12 Correct 2546 ms 141544 KB Output is correct
13 Correct 1546 ms 141544 KB Output is correct
14 Correct 5599 ms 141544 KB Output is correct
15 Correct 5963 ms 141544 KB Output is correct
16 Correct 3563 ms 134020 KB Output is correct
17 Correct 5979 ms 141544 KB Output is correct
18 Correct 5106 ms 141544 KB Output is correct
19 Correct 2553 ms 141544 KB Output is correct
20 Correct 8489 ms 141544 KB Output is correct
21 Correct 1276 ms 141544 KB Output is correct
22 Correct 8989 ms 141544 KB Output is correct
23 Correct 1693 ms 141544 KB Output is correct
24 Correct 7073 ms 134020 KB Output is correct
25 Correct 12873 ms 141544 KB Output is correct
26 Correct 10519 ms 141544 KB Output is correct
27 Correct 9499 ms 141544 KB Output is correct
28 Correct 2813 ms 141544 KB Output is correct
29 Correct 4026 ms 141544 KB Output is correct
30 Correct 12069 ms 141544 KB Output is correct
31 Correct 10289 ms 141544 KB Output is correct
32 Correct 1286 ms 141544 KB Output is correct
33 Correct 2359 ms 141544 KB Output is correct
34 Correct 3006 ms 141544 KB Output is correct
35 Correct 6769 ms 134152 KB Output is correct
36 Execution timed out 13000 ms 141544 KB Execution timed out
37 Halted 0 ms 0 KB -