Submission #151676

#	Time	Username	Problem	Language	Result	Execution time	Memory
151676		qkxwsm	Game (IOI13_game)	C++14	0 / 100	3 ms	504 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define y1 qwertyuiop
#define y2 asdfghjkl
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M;

ll gcd(ll a, ll b)
{
	return (b == 0 ? a : gcd(b, a % b));
}

struct node
{
	int idx, pri;
	ll cur, stor;
	node *ch[2];
	node(int x, ll v)
	{
		idx = x; pri = (rand() << 15 + rand()) % INF;
		cur = v; stor = v;
		ch[0] = nullptr; ch[1] = nullptr;
	}
};

void pull(node *t)
{
	if (!t) return;
	t -> stor = t -> cur;
	if (t -> ch[0]) t -> stor = gcd(t -> stor, t -> ch[0] -> stor);
	if (t -> ch[1]) t -> stor = gcd(t -> stor, t -> ch[1] -> stor);
	return;
}
typedef pair<node*, node*> pnn;
node *merge(node *l, node *r)
{
	if (!l) return r;
	if (!r) return l;
	if (l -> pri > r -> pri)
	{
		l -> ch[1] = merge(l -> ch[1], r);
		pull(l); return l;
	}
	else
	{
		r -> ch[0] = merge(l, r -> ch[0]);
		pull(r); return r;
	}
}
pnn split(node *t, int v)
{
	if (!t) return {t, t};
	int cur = t -> idx;
	if (v > cur)
	{
		pnn p = split(t -> ch[1], v);
		t -> ch[1] = p.fi; pull(t);
		return {t, p.se};
	}
	else
	{
		pnn p = split(t -> ch[0], v);
		t -> ch[0] = p.se; pull(t);
		return {p.fi, t};
	}
}

void inorder(node *t)
{
	if (!t) return;
	inorder(t -> ch[0]);
	cerr << t -> idx << ',' << t -> cur << ' ';
	inorder(t -> ch[1]);
}

struct Node
{
	node *root;
	Node *ch[2];
	Node()
	{
		root = nullptr;
		ch[0] = nullptr;
		ch[1] = nullptr;
	}
};

Node *root;

Node* upd(Node *t, int L, int R, int a, int y, ll v)
{
	if (!t) t = new Node();
	pnn p = split(t -> root, y), p1 = split(p.se, y + 1);
	t -> root = merge(p.fi, merge(new node(y, v), p1.se));
	// cerr << "PUSH\n";
	// cerr << L << " -> " << R << endl;
	// inorder(t -> root);
	// cerr << endl;
	if (L != R)
	{
		int mid = (L + R) >> 1;
		if (a <= mid)
		{
			t -> ch[0] = upd(t -> ch[0], L, mid, a, y, v);
		}
		else
		{
			t -> ch[1] = upd(t -> ch[1], mid + 1, R, a, y, v);
		}
	}
	return t;
}
ll qry(Node *t, int L, int R, int a, int b, int y1, int y2)
{
	// cerr << (t ? "YES" : "NO") << endl;
	// cerr << "WORK " << y1 << ' ' << y2 << endl;
	if (!t) return 0;
	if (a <= L && R <= b)
	{
		// cerr << "PULL\n";
		// cerr << L << " -> " << R << endl;
		// inorder(t -> root);
		// cerr << endl;
		pnn p = split(t -> root, y1), p1 = split(p.se, y2 + 1);
		// cerr << "SOLVE\n";
		// cerr << L << " -> " << R << endl;
		// inorder(p1.fi);
		// cerr << endl;
		ll res = (p1.fi ? p1.fi -> stor : 0);
		t -> root = merge(p.fi, merge(p1.fi, p1.se));
		return res;
	}
	int mid = (L + R) >> 1;
	if (b <= mid) return qry(t -> ch[0], L, mid, a, b, y1, y2);
	if (mid < a) return qry(t -> ch[1], mid + 1, R, a, b, y1, y2);
	return gcd(qry(t -> ch[0], L, mid, a, b, y1, y2), qry(t -> ch[1], mid + 1, R, a, b, y1, y2));
}

void init(int n, int m)
{
	N = n; M = m;
	srand(69);
}

void update(int x, int y, ll v)
{
	root = upd(root, 0, N - 1, x, y, v);
}

ll calculate(int x1, int y1, int x2, int y2)
{
	// cerr << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
	return qry(root, 0, N - 1, x1, x2, y1, y2);
}

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;
      ^~~
game.cpp: In constructor 'node::node(int, ll)':
game.cpp:55:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   idx = x; pri = (rand() << 15 + rand()) % INF;
                             ~~~^~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20