Submission #1181965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181965		sano	Game (IOI13_game)	C++20	100 / 100	5042 ms	46976 KiB

game

#pragma GCC optimize("O3")
#pragma GCC target("tune=native")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "game.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

ll nsd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

class treap {
	struct node {
		node* l = nullptr;
		node* r = nullptr;
		ll val, nsd;
		int key, priority;
		node(ll val1, int key1) {
			val = val1, key = key1;
			priority = rand();
			nsd = val1;
		}
	};
	typedef node* pnode;
	pnode root = nullptr;

	ll get_nsd(pnode& t) {
		if (!t) return 0;
		return t->nsd;
	}

	void update(pnode t) {
		if (!t) return;
		t->nsd = nsd(nsd(get_nsd(t->l), get_nsd(t->r)), t->val);
		return;
	}

	bool porovnaj(int a1, int a2, int b1, int b2) {
		if (a1 == b1) {
			return a2 > b2;
		}
		return a1 > b1;
	}

	void split(pnode t, int key, pnode& l, pnode& r) {
		if (!t) {
			l = r = nullptr;
			return;
		}
		if (t->key >= key) {
			split(t->l, key, l, t->l);
			r = t;
		}
		else {
			split(t->r, key, t->r, r);
			l = t;
		}
		update(t);
		return;
	}
	void merge(pnode& t, pnode l, pnode r) {
		if (!l || !r) {
			t = l ? l : r;
			return;
		}
		if (l->priority > r->priority) {
			merge(l->r, l->r, r);
			t = l;
		}
		else {
			merge(r->l, l, r->l);
			t = r;
		}
		update(t);
		return;
	}
	void insert(pnode& t, pnode x) {
		if (!t) {
			t = x;
			return;
		}
		if (x->priority > t->priority) {
			split(t, x->key, x->l, x->r);
			t = x;
		}
		else {
			insert(t->key >= x->key ? t->l : t->r, x);
		}
		update(t);
		return;
	}

	bool najdi(pnode t, int key, ll val) {
		if (!t) return 0;
		bool odp = 0;
		if (t->key == key) {
			t->val = val;
			odp = 1;
		}
		else {
			odp = najdi(t->key >= key ? t->l : t->r, key, val);
		}
		update(t);
		return odp;
	}

public:
	void zmen(int key, ll val) {
		bool mame = najdi(root, key, val);
		if (!mame) insert(root, new node(val, key));
		return;
	}
	ll daj(int a, int b) {
		pnode l, r;
		l = r = nullptr;
		split(root, a, root, r);
		split(r, b + 1, l, r);
		ll odp = get_nsd(l);
		merge(root, root, l);
		merge(root, root, r);
		return odp;
	}

};

class intervalac {
	int n;
	static const int MAX_SEG_NODES = 30000; // again, estimate high enough

	struct node {
		node* l = nullptr;
		node* r = nullptr;
		treap in;
	};



	node seg_nodes[MAX_SEG_NODES];
	int seg_node_cnt = 0;

	typedef node* pnode;
	pnode root = new node;

	ll get_range(pnode t, int b) {
		return t ? t->in.daj(b, b) : 0;
	}

	void zmen(pnode& t, int l, int r, int a, int b, ll k) {
		if (a > r || a < l) return;
		if (!t) t = new node;
		if (r == l) {
			t->in.zmen(b, k);
			return;
		}
		int m = (l + r) / 2;
		zmen(t->l, l, m, a, b, k); zmen(t->r, m + 1, r, a, b, k);
		t->in.zmen(b, nsd(get_range(t->l, b), get_range(t->r, b)));
		return;
	}

	ll daj(pnode& t, int l, int r, int a, int b, int c, int d) {
		if (a > r || b < l) return 0;
		if (!t) return 0;
		if (a <= l && r <= b) {
			return t->in.daj(c, d);
		}
		int m = (l + r) / 2;
		return nsd(daj(t->l, l, m, a, b, c, d), daj(t->r, m + 1, r, a, b, c, d));
	}

public:
	void postav(int vel) {
		n = vel;
		return;
	}
	void zmen(int p, int q, ll k) {
		zmen(root, 0, n - 1, p, q, k);
		return;
	}
	ll daj(int p, int q, int u, int v) {
		return daj(root, 0, n - 1, p, q, u, v);
	}
};

intervalac seg;

void init(int r2, int c2) {
	int r = r2, c = c2;
	seg.postav(r);
	return;
}

void update(int p, int q, ll k) {
	seg.zmen(p, q, k);
	return;
}

ll calculate(int p, int q, int u, int v) {
	return seg.daj(p, u, q, v);
}

/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int r, c, q; cin >> r >> c >> q;
	init(r, c);
	For(i, q) {
		int t; cin >> t;
		if (t == 1) {
			int p, q; ll k; cin >> p >> q >> k;
			update(p, q, k);
		}
		if (t == 2) {
			int p, q, u, v;
			cin >> p >> q >> u >> v;
			cout << calculate(p, q, u, v) << '\n';
		}
	}
	return 0;
}*/

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