Submission #653890

#	Time	Username	Problem	Language	Result	Execution time	Memory
653890		vovamr	Game (IOI13_game)	C++17	100 / 100	6997 ms	67528 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline ll gcd(const ll &a, const ll &b) { return (!b ? a : gcd(b, a % b)); }

struct node {
	node *l = nullptr;
	node *r = nullptr;
	int p;
	pii key;
	ll val, g;
	node(const pii &key, const ll &x) : key(key), val(x), g(x) { p = rng() % INT_MAX; }
}; typedef node* nd;
inline ll val(nd t) { return !t ? 0 : t->val; }
inline ll g(nd t) { return !t ? 0 : t->g; }
inline void upd(nd t) { if (!t) return; t->g = gcd(gcd(g(t->l), g(t->r)), t->val); }
inline nd mg(nd a, nd b) {
	if (!a || !b) return !a ? b : a;
	if (a->p > b->p) { a->r = mg(a->r, b); upd(a); return a; }
	else { b->l = mg(a, b->l); upd(b); return b; }
}
inline pair<nd,nd> sp(nd t, pii x) {
	if (!t) return {nullptr,nullptr};
	if (t->key <= x) { auto tt = sp(t->r, x); t->r = tt.fi; upd(t); return {t, tt.se}; }
	else { auto tt = sp(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline void ins(nd &t, pii pos, ll x) {
	auto [t1, t2] = sp(t, mpp(pos.fi, pos.se - 1));
	auto [t3, t4] = sp(t2, pos);
	t = mg(mg(t1, new node(pos, x)), t4);
}
inline ll get1(nd &t, int l, int r) {
	auto [t1, t2] = sp(t, mpp(l - 1, iinf));
	auto [t3, t4] = sp(t2, mpp(r, iinf));
	ll res = g(t3);
	t = mg(t1, mg(t3, t4));
	return res;
}

struct Node {
	Node *l = nullptr;
	Node *r = nullptr;
	nd st = nullptr;
	Node() {}
}; Node *t = new Node();

inline void upd(Node *&v, int vl, int vr, int x, int y, ll d) {
	if (!v) v = new Node();
	ins(v->st, mpp(y, x), d);
	if (vl == vr) return;
	int m = vl + vr >> 1;
	if (x <= m) upd(v->l, vl, m, x, y, d);
	else upd(v->r, m + 1, vr, x, y, d);
}
inline ll get(Node *v, int vl, int vr, int lx, int rx, int ly, int ry) {
	if (lx > rx || !v) return 0ll;
	else if (vl == lx && vr == rx) return get1(v->st, ly, ry);
	int m = vl + vr >> 1;
	return gcd(get(v->l,vl,m,lx,min(rx,m),ly,ry),
			get(v->r,m+1,vr,max(lx,m+1),rx,ly,ry));
}

int l1, r1;
void init(int R, int C) {
	l1 = 0, r1 = R - 1;
}

void update(int P, int Q, long long K) {
	upd(t, l1, r1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	return get(t, l1, r1, P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'void upd(Node*&, int, int, int, int, long long int)':
game.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int m = vl + vr >> 1;
      |          ~~~^~~~
game.cpp: In function 'long long int get(Node*, int, int, int, int, int, int)':
game.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int m = vl + vr >> 1;
      |          ~~~^~~~

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