Submission #972312

#	Time	Username	Problem	Language	Result	Execution time	Memory
972312		midi	Game (IOI13_game)	C++14	0 / 100	105 ms	256000 KiB

game

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

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef map<ll,ll> mapll;
#define umap unordered_map
typedef umap<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))

#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)

#define mxQ (22'010ll)
#define lgN (30ll)
#define sgN (1ll<<30ll)
#define MAXNODES (mxQ*lgN*lgN*4)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

struct nd
{
	ll g;
	nd *l, *r;
	nd () { g=0; l=r=nullptr; }
} nds[MAXNODES];
ll sz;

nd *new_nd() { return nds+sz++; }

struct st2
{

	ll g(nd *&u) { return u ? u->g : 0; }
	nd *root;

	ll upd (nd *&u, ll l, ll r, ll j, ll x)
	{
		if (j<l or r<=j) return g(u);
		if (!u) u=new_nd();
		if (l+1==r) return u->g=x;
		ll m=(l+r)/2;
		return u->g = GCD (upd (u->l, l, m, j, x), upd (u->r, m, r, j, x));
	}

	void upd (ll j, ll x) { upd (root, 0, sgN, j, x); }

	ll qry (nd *&u, ll lt, ll rt, ll l, ll r)
	{
		if (rt<=l or r<=lt or !u) return 0;
		if (l<=lt and rt<=r) return u->g;
		ll mt=(lt+rt)/2;
		return GCD(qry (u->l, lt, mt, l, r), qry (u->r, mt, rt, l, r));
	}

	ll qry (ll l, ll r) { return qry (root, 0, sgN, l, r+1); }
};

struct st
{
	struct nd2
	{
		nd2 *l, *r;
		st2 st;
	} *root;

	void upd (nd2 *&u, ll lt, ll rt, ll l, ll r, ll x)
	{
		// printf("lt: %lli, rt: %lli\n", lt, rt);
		if (!u) u=new nd2;
		if (l<lt or rt<=l) return;
		u->st.upd(r, x);
		if (lt+1==rt) return;
		ll mt=(lt+rt)/2;
		upd (u->l, lt, mt, l, r, x);
		upd (u->r, mt, rt, l, r, x);
	}

	void upd (ll l, ll r, ll x) { upd (root, 0, sgN, l, r, x); }

	ll qry (nd2 *&u, ll lt, ll rt, ll l, ll r, prll sender)
	{
		if (rt<=l or r<=lt or !u) return 0;
		if (l<=lt and rt<=r) return u->st.qry(sender.fi, sender.se);
		ll mt=(lt+rt)/2;
		return qry (u->l, lt, mt, l, r, sender) + qry (u->r, mt, rt, l, r, sender);
	}

	ll qry (ll l1, ll r1, ll l2, ll r2) { return qry (root, 0, sgN, l1, r1+1, {l2, r2}); }
} st;

void tassert (ll b)
{
	if (!b) while (1) ;
}

void init (int n, int m) { sz=0; }
void update (int l, int r, ll x)
{
	tassert(0);
	st.upd(l,r,x);
}
ll calculate (int l1, int r1, int l2, int r2)
{
	tassert(0);
	return st.qry(l1, l2, r1, r2);
}

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