Submission #1030031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030031		tolbi	Game (IOI13_game)	C++17	0 / 100	1 ms	364 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;
	}
};
#define tol(bi) ((1LL<<((int)(bi))))
struct SegTree{
	vector<Treap> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1);
	}
	void update(int x, int y, ll val){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		while (l<r){
			int mid = l+(r-l)/2;
			segtree[node].update(y,val);
			if (mid>=x){
				node=node*2+1;
				r=mid;
			}
			else {
				node=node*2+2;
				l=mid+1;
			}
		}
		segtree[node].update(y,val);
	}
	ll query(int tl, int tr, int a, int b, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr) return segtree[node].query(a,b);
		if (l>tr || r<tl) return 0;
		int mid = l+(r-l)/2;
		ll ret = 0;
		if (mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node*2+1));
		if (mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node*2+2));
		return ret;
	}
} *segtree;
void init(int R, int C) {
	segtree = new SegTree(R);
}

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20