Submission #1118605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118605		xnqs	Game (IOI13_game)	C++17	100 / 100	5405 ms	72096 KiB

game

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>
#include <unordered_map>
#include <cassert>

#include "game.h"

std::mt19937 rng(53);

/*long long std::__gcd(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}*/

namespace Treap {
struct Node {
	std::pair<int,int> p;
	int64_t val; // y, x
	int64_t gcd;
	int size;
	int prio;
	Node* l;
	Node* r;
	Node(std::pair<int,int> p, int64_t val):
		p(p), val(val), gcd(val), size(1), prio(rng()), l(nullptr), r(nullptr) {}
	~Node() {
		if (l) {
			delete l;
		}
		if (r) {
			delete r;
		}
	}
};

Node* _aux_split_l = nullptr;
Node* _aux_split_r = nullptr;
Node* _aux_merge = nullptr;

int GetNodeSize(Node* node) {
	if (!node) {
		return 0;
	}
	return node->size;
}

int64_t GetNodeGCD(Node* node) {
	if (!node) {
		return 0;
	}
	return node->gcd;
}

void NodeUpdate(Node* node) {
	if (!node) {
		return;
	}

	node->size = 1;
	node->gcd = node->val;
	if (node->l) {
		node->size += node->l->size;
		node->gcd = std::__gcd(node->gcd, node->l->gcd);
	}
	if (node->r) {
		node->size += node->r->size;
		node->gcd = std::__gcd(node->gcd, node->r->gcd);
	}
}

// l < key, r >= key
void SplitDriver(Node* node, int key) {
	if (!node) {
		_aux_split_l = _aux_split_r = nullptr;
		return;
	}

	int node_key = GetNodeSize(node->l);
	if (key-node_key-1>=0) {
		SplitDriver(node->r,key-node_key-1);
		node->r = _aux_split_l;
		_aux_split_l = node;
		NodeUpdate(node);
	}
	else {
		SplitDriver(node->l,key);
		node->l = _aux_split_r;
		_aux_split_r = node;
		NodeUpdate(node);
	}
}

std::pair<Node*, Node*> Split(Node* node, int key) {
	SplitDriver(node,key);
	return {_aux_split_l, _aux_split_r};
}

void MergeDriver(Node* a, Node* b) {
	if (!a) {
		_aux_merge = b;
		return;
	}
	if (!b) {
		_aux_merge = a;
		return;
	}

	if (a->prio > b->prio) {
		MergeDriver(a->r,b);
		a->r = _aux_merge;
		_aux_merge = a;
		NodeUpdate(a);
	}
	else {
		MergeDriver(a,b->l);
		b->l = _aux_merge;
		_aux_merge = b;
		NodeUpdate(b);
	}
}

Node* Merge(Node* a, Node* b) {
	MergeDriver(a,b);
	return _aux_merge;
}

Node* Insert(Node*& root, int pos, std::pair<int,int> p, int64_t val) {
	if (!root) {
		return root = new Node(p, val);
	}

	auto trees = Split(root,pos);
	return root = Merge(Merge(trees.first, new Node(p, val)), trees.second);
}

Node* Remove(Node*& root, int pos) {
	if (!root) {
		return root;
	}

	auto trees = Split(root,pos);
	auto trees_right = Split(trees.second,1);
	delete trees_right.first;
	return root = Merge(trees.first,trees_right.second);
}

int LowerBound(Node* node, std::pair<int,int> p, int skipped = 0, int depth = 0) {
	if (!node) {
		return 0x3f3f3f3f;
	}

	int node_key = skipped + GetNodeSize(node->l);
	if (node->p >= p) {
		return std::min(node_key, LowerBound(node->l, p, skipped, 1));
	}
	else {
		return LowerBound(node->r, p, node_key+1, 1);
	}
}

int UpperBound(Node* node, std::pair<int,int> p, int skipped = 0, int depth = 0) {
	if (!node) {
		return -1;
	}

	int node_key = skipped + GetNodeSize(node->l);
	if (node->p <= p) {
		return std::max(node_key, UpperBound(node->r, p, node_key+1));
	}
	else {
		return UpperBound(node->l, p, skipped);
	}
}

int64_t RangeGCDQuery(Node*& root, int l, int r) {
	if (!root) {
		return 0;
	}

	auto trees = Split(root,l);
	auto trees_right = Split(trees.second,r-l+1);
	int64_t ret = GetNodeGCD(trees_right.first);
	root = Merge(Merge(trees.first,trees_right.first),trees_right.second);
	return ret;
}

std::pair<int,int> GetKth(Node*& node, int k, int skipped = 0) {
	//std::cout << Treap::GetNodeSize(node) << " " << k << "\n";
	if (!node) {
		return {-1, -1};
	}
	
	int node_key = skipped + GetNodeSize(node->l);
	if (node_key==k) {
		return node->p;
	}
	else if (node_key>k) {
		return GetKth(node->l,k,skipped);
	}
	else {
		return GetKth(node->r,k,node_key+1);
	}

	/*auto trees = Split(node,k);
	auto trees_right = Split(trees.second,1);
	auto ret = trees_right.first->p;
	node = Merge(Merge(trees.first,trees_right.first),trees_right.second);
	return ret;*/
}
};

struct SegTreeNode {
	Treap::Node* treap = nullptr;
	SegTreeNode* l = nullptr;
	SegTreeNode* r = nullptr;

	~SegTreeNode() {
		if (l) {
			delete l;
		}
		if (r) {
			delete r;
		}
	}
};

int r, c;
SegTreeNode* root = nullptr;
std::unordered_map<int, std::unordered_map<int, int64_t>> arr;

void Insert(SegTreeNode* node, int l, int r, int x, int y, int64_t val) {
	std::pair<int,int> p(y,x);
	int pos = Treap::LowerBound(node->treap, p);
	if (pos==0x3f3f3f3f) {
		pos = Treap::GetNodeSize(node->treap);
	}
	node->treap = Treap::Insert(node->treap, pos, p, val);

	if (l==r) {
		return;
	}

	int m = (l+r)>>1;
	if (x<=m) {
		if (!node->l) {
			node->l = new SegTreeNode;
		}
		Insert(node->l,l,m,x,y,val);
	}
	else {
		if (!node->r) {
			node->r = new SegTreeNode;
		}
		Insert(node->r,m+1,r,x,y,val);
	}
}

void Remove(SegTreeNode* node, int l, int r, int x, int y) {
	std::pair<int,int> p(y,x);
	int pos = Treap::LowerBound(node->treap, p);
	assert(pos != 0x3f3f3f3f);
	node->treap = Treap::Remove(node->treap, pos);

	if (l==r) {
		return;
	}

	int m = (l+r)>>1;
	if (x<=m) {
		Remove(node->l,l,m,x,y);
	}
	else {
		Remove(node->r,m+1,r,x,y);
	}
}

int64_t Query(SegTreeNode* node, int l, int r, int st, int fi, int a, int b) {
	if (!node) {
		return 0;
	}
	if (l>fi||r<st) {
		return 0;
	}
	if (st<=l&&r<=fi) {
		std::pair<int,int> pl(a,-1);
		std::pair<int,int> pr(b+1,-1);

		int le = Treap::LowerBound(node->treap, pl);
		int ri = Treap::UpperBound(node->treap, pr);
		if (le==0x3f3f3f3f) {
			le = Treap::GetNodeSize(node->treap);
		}

		if (le==0x3f3f3f3f||ri==-1||le>ri) {
			return 0;
		}
		else {
			return Treap::RangeGCDQuery(node->treap, le, ri);
		}
	}

	int m = (l+r)>>1;
	return std::__gcd(Query(node->l,l,m,st,fi,a,b), Query(node->r,m+1,r,st,fi,a,b));
}

void init(int R, int C) {
	r = R;
	c = C;

	root = new SegTreeNode;
}

void update(int P, int Q, long long K) {
	if (arr[P].count(Q)) {
		arr[P].erase(Q);
		Remove(root, 0, r-1, P, Q);
	}

	arr[P][Q] = K;
	Insert(root, 0, r-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	return Query(root, 0, r-1, P, U, Q, V);
}

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