Submission #653882

#	Time	Username	Problem	Language	Result	Execution time	Memory
653882		vovamr	Game (IOI13_game)	C++17	63 / 100	1483 ms	24048 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;
	ll g;
	node(ll x = 0) : g(x) {}
};
inline void upd1(node *&v, int vl, int vr, int pos, const ll &x) {
//	cout << "getting " << pos << " on [" << vl << ", " << vr << "]" << '\n';
	if (!v) v = new node();
	if (vl == vr) return void(v->g = x);
	int m = vl + vr >> 1;
	if (pos <= m) upd1(v->l, vl, m, pos, x);
	else upd1(v->r, m + 1, vr, pos, x);
	v->g = gcd(!v->l ? 0 : v->l->g, !v->r ? 0 : v->r->g);
}
inline ll get1(node *v, int vl, int vr, int l, int r) {
//	cout << "getting " << l << ", " << r << " on [" << vl << ", " << vr << "]" << '\n';
	if (l > r || !v) return 0ll;
	else if (vl == l && vr == r) return v->g;
	int m = vl + vr >> 1;
	return gcd(get1(v->l,vl,m,l,min(r,m)),
			get1(v->r,m+1,vr,max(l,m+1),r));
}
inline void rec1(node *&v, node *a, node *b, int vl, int vr, int pos) {
	if (!v) v = new node();
	v->g = gcd(!a ? 0 : a->g, !b ? 0 : b->g);
	if (vl == vr) return;
	int m = vl + vr >> 1;
	if (pos <= m) rec1(v->l, !a ? nullptr : a->l, !b ? nullptr : b->l, vl, m, pos);
	else rec1(v->r, !a ? nullptr : a->r, !b ? nullptr : b->r, m + 1, vr, pos);
}

inline void dbg(node *v, int vl, int vr, int lx, int rx) {
	cout << "[" << lx << ", " << rx << "] * [" << vl << ", " << vr << "]: " << (!v ? 0 : v->g) << '\n';
	if (vl == vr) return;
	int m = vl + vr >> 1;
	dbg(!v ? nullptr : v->l, vl, m, lx, rx);
	dbg(!v ? nullptr : v->r, m + 1, vr, lx, rx);
}

struct seg2d {
	int n, L, R;
	ve<node*> t;
	seg2d(int n = 0, int L = 0, int R = 0) : n(n), L(L), R(R) { t.resize(4 * n); }
	inline void upd(int v, int vl, int vr, int x, int y, ll d) {
		if (vl == vr) {
			upd1(t[v], L, R, y, d);
			return;
		}
		int m = vl + vr >> 1;
		if (x <= m) upd(2 * v + 1, vl, m, x, y, d);
		else upd(2 * v + 2, m + 1, vr, x, y, d);
		rec1(t[v], t[2 * v + 1], t[2 * v + 2], L, R, y);
	}
	inline ll get(int v, int vl, int vr, int lx, int rx, int ly, int ry) {
		if (lx > rx || !t[v]) return 0ll;
		else if (vl == lx && vr == rx) return get1(t[v], L, R, ly, ry);
		int m = vl + vr >> 1;
		return gcd(get(2*v+1,vl,m,lx,min(rx,m),ly,ry),
				get(2*v+2,m+1,vr,max(lx,m+1),rx,ly,ry));
	}

	inline void upd(int x, int y, ll d) { upd(0, 0, n - 1, x, y, d); }
	inline ll get(int lx, int rx, int ly, int ry) { return get(0, 0, n - 1, lx, rx, ly, ry); }

	inline void debug(int v, int vl, int vr) {
		dbg(t[v], L, R, vl, vr);
		if (vl == vr) return;
		int m = vl + vr >> 1;
		debug(2 * v + 1, vl, m);
		debug(2 * v + 2, m + 1, vr);
	}
	inline void debug() { debug(0, 0, n - 1); }
};

seg2d st;

void init(int R, int C) {
	st = seg2d(R, 0, C - 1);
}

void update(int P, int Q, long long K) {
	st.upd(P, Q, K);
//	st.debug();
//	cout << '\n' << '\n';
}

long long calculate(int P, int Q, int U, int V) {
	return st.get(P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'void upd1(node*&, int, int, int, const long long int&)':
game.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int m = vl + vr >> 1;
      |          ~~~^~~~
game.cpp: In function 'long long int get1(node*, int, int, int, int)':
game.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int m = vl + vr >> 1;
      |          ~~~^~~~
game.cpp: In function 'void rec1(node*&, node*, node*, int, int, int)':
game.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int m = vl + vr >> 1;
      |          ~~~^~~~
game.cpp: In function 'void dbg(node*, int, int, int, int)':
game.cpp:61:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int m = vl + vr >> 1;
      |          ~~~^~~~
game.cpp: In member function 'void seg2d::upd(int, int, int, int, int, long long int)':
game.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int m = vl + vr >> 1;
      |           ~~~^~~~
game.cpp: In member function 'long long int seg2d::get(int, int, int, int, int, int, int)':
game.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int m = vl + vr >> 1;
      |           ~~~^~~~
game.cpp: In member function 'void seg2d::debug(int, int, int)':
game.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int m = vl + vr >> 1;
      |           ~~~^~~~

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