Submission #38638

#	Time	Username	Problem	Language	Result	Execution time	Memory
38638		alenam0161	Game (IOI13_game)	C++14	100 / 100	6976 ms	185152 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20