Submission #1248536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248536		RomanLeshchuk	Game (IOI13_game)	C++20	0 / 100	0 ms	328 KiB

game

#include "game.h"

#include <iostream>
#include <numeric>
#include <cmath>

using namespace std;

struct TreapNode
{
	int pos;
	long long val;
	long long totVal;
	int priority;
	int size;
	TreapNode* l;
	TreapNode* r;
};

struct Node
{
	TreapNode* val;
	Node* l;
	Node* r;
};

int maxTreapVal;
int segTreeSize;
Node* tree = nullptr;

void recalc(TreapNode* node)
{
	node->totVal = gcd(node->val, gcd(node->l ? node->l->totVal : 0, node->r ? node->r->totVal : 0));
	node->size = (node->l ? node->l->size : 0) + (node->r ? node->r->size : 0) + 1;
}

TreapNode* rotateL(TreapNode* p)
{
	TreapNode* newP = p->r;
	p->r = newP->l;
	newP->l = p;
	recalc(p);
	return newP;
}

TreapNode* rotateR(TreapNode* p)
{
	TreapNode* newP = p->l;
	p->l = newP->r;
	newP->r = p;
	recalc(p);
	return newP;
}

long long queryTreap(TreapNode* node, int l, int r, int ql, int qr)
{
	if (!node || qr < l || r < ql)
	{
		return 0;
	}
	if (ql <= l && r <= qr)
	{
		return node->totVal;
	}
	long long lRes = queryTreap(node->l, l, node->pos - 1, ql, qr);
	long long rRes = queryTreap(node->r, node->pos + 1, r, ql, qr);
	return gcd(ql <= node->pos && node->pos <= qr ? node->val : 0, gcd(lRes, rRes));
}

TreapNode* insert(TreapNode* node, const TreapNode& upd)
{
	if (!node)
	{
		return new TreapNode{ upd };
	}
	
	if (upd.pos == node->pos)
	{
		node->val = upd.val;
	}
	else if (upd.pos < node->pos)
	{
		node->l = insert(node->l, upd);
		if (node->priority < node->l->priority)
		{
			node = rotateR(node);
		}
	}
	else
	{
		node->r = insert(node->r, upd);
		if (node->priority < node->r->priority)
		{
			node = rotateL(node);
		}
	}
	
	recalc(node);

	return node;
}

Node* updateSegtree(Node* node, int l, int r, int i, int j, long long val)
{
	if (!node)
	{
		node = new Node{ nullptr, nullptr, nullptr };
	}

	node->val = insert(node->val, { j, val, val, rand(), 1, nullptr, nullptr });
	
	if (l == r)
	{
		return node;
	}
	
	int mid = (l + r) / 2;
	if (i <= mid)
	{
		node->l = updateSegtree(node->l, l, mid, i, j, val);
	}
	else
	{
		node->r = updateSegtree(node->r, mid + 1, r, i, j, val);
	}
	
	return node;
}

long long query(Node* node, int l, int r, int li, int ri, int lj, int rj)
{
	if (!node || r < li || ri < l)
	{
		return 0;
	}

	if (li <= l && r <= ri)
	{
		return queryTreap(node->val, 0, maxTreapVal, lj, rj);
	}
	
	int mid = (l + r) / 2;
	long long lRes = query(node->l, l, mid, li, ri, lj, rj);
	long long rRes = query(node->r, mid + 1, r, li, ri, lj, rj);
	return gcd(lRes, rRes);
}

void init(int R, int C)
{
	segTreeSize = 1 << (int)ceil(log2(R));
	maxTreapVal = C - 1;
}

void update(int P, int Q, long long K)
{
	tree = updateSegtree(tree, 0, segTreeSize - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
	return query(tree, 0, segTreeSize - 1, P, U, Q, V);
}

/*
int main()
{
	init(2, 3);
	update(0, 0, 20);
	update(0, 2, 15);
	update(1, 1, 12);
	cout << calculate(0, 0, 0, 2) << '\n';
	cout << calculate(0, 0, 1, 1) << '\n';
	update(0, 1, 6);
	update(1, 1, 14);
	cout << calculate(0, 0, 0, 2) << '\n';
	cout << calculate(0, 0, 1, 1) << '\n';
	return 0;
}
*/

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