Submission #595734

#	Time	Username	Problem	Language	Result	Execution time	Memory
595734		Bobaa	Game (IOI13_game)	C++17	100 / 100	2888 ms	73268 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std; 

mt19937 rng(time(0)); 

struct TreapNode {
	TreapNode *l, *r; 
	int pos, key, mn, mx; 
	long long val, g; 
	
	TreapNode(int position, long long value) {
		l = r = nullptr; 
		mn = mx = pos = position; 
		key = rng(); 
		val = g = value; 
	}
	
	void update() {
		g = val; 
		if (l) g = __gcd(g, l -> g); 
		if (r) g = __gcd(g, r -> g); 
		mn = (l ? l -> mn : pos); 
		mx = (r ? r -> mx : pos); 
	}
};

struct Treap {
	TreapNode *root; 
	
	Treap() {
		root = nullptr; 
	}
	
	void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
		if (t == nullptr) {
			l = r = nullptr; 
			return; 
		}
		if (t -> pos < pos) {
			split(t -> r, pos, l, r); 
			t -> r = l; 
			l = t; 
		} else {
			split(t -> l, pos, l, r); 
			t -> l = r; 
			r = t; 
		}
		t -> update(); 
	}
	
	TreapNode* merge(TreapNode *l, TreapNode *r) {
		if (!l) return r; 
		if (!r) return l;
		if (l -> key < r -> key) {
			l -> r = merge(l -> r, r); 
			l -> update(); 
			return l; 
		} else {
			r -> l = merge(l, r -> l); 
			r -> update(); 
			return r; 
		}
	}
	
	bool find(int pos) {
		TreapNode *t = root; 
		while (t) {
			if (t -> pos == pos) return true; 
			if (t -> pos > pos) t = t -> l; 
			else t = t -> r; 
		}
		return false; 
	}
	
	void update(TreapNode *t, int pos, long long value) {
		if (t -> pos == pos) {
			t -> val = value; 
			t -> update(); 
			return; 
		}
		if (t -> pos > pos) update(t -> l, pos, value); 
		else update(t -> r, pos, value); 
		t -> update(); 
	}
	
	void insert(int pos, long long value) {
		if (find(pos)) {
			update(root, pos, value); 
			return; 
		}
		TreapNode *l, *r; 
		split(root, pos, l, r); 
		root = merge(merge(l, new TreapNode(pos, value)), r); 
	}
	
	long long query(TreapNode *t, int l, int r) {
		if (t -> mx < l || t -> mn > r) return 0LL; 
		if (l <= t -> mn && t -> mx <= r) return t -> g; 
		long long res = 0; 
		if (l <= t -> pos && t -> pos <= r) res = t -> val; 
		if (t -> l) res = __gcd(res, query(t -> l, l, r)); 
		if (t -> r) res = __gcd(res, query(t -> r, l, r)); 
		return res; 
	}
	
	long long query(int l, int r) {
		if (!root) return 0LL; 
		return query(root, l, r); 
	}
}; 

struct SegTree {
	SegTree *l, *r; 
	Treap treap; 
	int lo, hi; 
	
	SegTree() {
		l = r = nullptr;
	}
	
	SegTree(int st, int en) {
		l = r = nullptr; 
		lo = st; 
		hi = en; 
	}
	
	void new_left() {
		if (!l) l = new SegTree(lo, (lo + hi) / 2); 
	}
	
	void new_right() {
		if (!r) r = new SegTree((lo + hi) / 2 + 1, hi); 
	}
	
	void fix(int pos) {
		long long val = 0; 
		if (l) val = __gcd(val, l -> treap.query(pos, pos)); 
		if (r) val = __gcd(val, r -> treap.query(pos, pos)); 
		treap.insert(pos, val); 
	}
	
	void update(int x, int y, long long val) {
		if (hi < x || lo > x) return; 
		if (lo == hi) {
			treap.insert(y, val); 
			return; 
		}
		int mid = (lo + hi) / 2; 
		if (x <= mid) {
			new_left(); 
			l -> update(x, y, val); 
		} else {
			new_right(); 
			r -> update(x, y, val); 
		}
		fix(y); 
	}
	
	long long query(int t, int b, int st, int en) {
		if (hi < t || lo > b) return 0LL; 
		if (t <= lo && hi <= b) return treap.query(st, en); 
		long long ans = 0; 
		if (l) ans = __gcd(ans, l -> query(t, b, st, en)); 
		if (r) ans = __gcd(ans, r -> query(t, b, st, en)); 
		return ans; 
	}
};

SegTree segtree; 

void init(int R, int C) {
	segtree = SegTree(0, R - 1); 
}

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); 
}

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