Submission #38628

#	Time	Username	Problem	Language	Result	Execution time	Memory
38628		alenam0161	Game (IOI13_game)	C++14	80 / 100	13000 ms	141544 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;
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 (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: 0 / 20