Submission #1030043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030043		tolbi	Game (IOI13_game)	C++17	100 / 100	4564 ms	67664 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Treap{
	struct Node{
		Node *lnode, *rnode;
		ll val, gg, h;
		int pos;
		Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
	} *root;
	Treap():root(nullptr){}
	void upd(Node* nd){
		nd->gg=nd->val;
		if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg);
		if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg);
	}
	Node* merge(Node* a, Node* b){
		if (!a || !b) return (a?a:b);
		if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a;
		return b->lnode = merge(a,b->lnode),upd(b),b;
	}
	pair<Node*, Node*> split(Node* node, int x){
		if (!node) return {nullptr,nullptr};
		if (node->pos>=x){
			pair<Node*, Node*> spl = split(node->lnode,x);
			node->lnode=spl.second;
			upd(node);
			return {spl.first,node};
		}
		pair<Node*, Node*> spl = split(node->rnode,x);
		node->rnode=spl.first;
		upd(node);
		return {node,spl.second};
	}
	void update(int x, ll val){
		if (root==nullptr){
			return root = new Node(x,val), void(23);
		}
		Node* nd = root;
		while (nd){
			if (nd->pos==x) break;
			if (nd->pos>x) nd=nd->lnode;
			else nd=nd->rnode;
		}
		if (nd==nullptr){
			Node* nnode = new Node(x,val);
			pair<Node*, Node*> spl = split(root,x);
			root=merge(spl.first,nnode);
			root=merge(root,spl.second);
		}
		else {
			vector<Node*> backtrack;
			nd->val=val;
			upd(nd);
			nd = root;
			while (nd->pos!=x){
				backtrack.push_back(nd);
				if (nd->pos>x) nd=nd->lnode;
				else nd=nd->rnode;
			}
			while (backtrack.size()){
				upd(backtrack.back());
				backtrack.pop_back();
			}
		}
	}
	ll query(int l, int r){
		pair<Node*, Node*> spl = split(root, l);
		pair<Node*, Node*> spl2 = split(spl.second, r+1);
		ll ret = 0;
		if (spl2.first) ret = spl2.first->gg;
		root = merge(spl2.first,spl2.second);
		root = merge(spl.first,root);
		return ret;
	}
};
constexpr int MAXN = 1000000000;
struct SegTree{
	struct Node{
		Node *lnode, *rnode;
		Treap tr;
		Node():lnode(nullptr),rnode(nullptr){}
	} *root;
	SegTree():root(new Node){}
	void update(int x, int y, ll val, int l = 0, int r = MAXN, Node* nd = nullptr){
		if (l==0 && r==MAXN) nd=root;
		if (l==r){
			return nd->tr.update(y,val);
		}
		int mid = l+(r-l)/2;
		if (mid>=x){
			if (nd->lnode==nullptr) nd->lnode=new Node;
			update(x,y,val,l,mid,nd->lnode);
		}
		else {
			if (nd->rnode==nullptr) nd->rnode=new Node;
			update(x,y,val,mid+1,r,nd->rnode);
		}
		ll ret = 0;
		if (nd->lnode) ret=nd->lnode->tr.query(y,y);
		if (nd->rnode) ret=gcd2(nd->rnode->tr.query(y,y),ret);
		nd->tr.update(y,ret);
	}
	ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){
		if (l==0 && r==MAXN) node=root;
		if (l>=tl && r<=tr) return node->tr.query(a,b);
		if (l>tr || r<tl) return 0;
		int mid = l+(r-l)/2;
		ll ret = 0;
		if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode));
		if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode));
		return ret;
	}
} segtree;
void init(int R, int C) {
	//23 severim
}

void update(int P, int Q, long long K) {
	segtree.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	return segtree.query(P,U,Q,V);
}

Compilation message (stderr)

game.cpp: In constructor 'Treap::Node::Node(int, ll)':
game.cpp:19:7: warning: 'Treap::Node::pos' will be initialized after [-Wreorder]
   19 |   int pos;
      |       ^~~
game.cpp:17:9: warning:   'Treap::Node* Treap::Node::lnode' [-Wreorder]
   17 |   Node *lnode, *rnode;
      |         ^~~~~
game.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
      |   ^~~~

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