oj.uz

Submission #313327

# Submission time Handle Problem Language Result Execution time Memory
313327 2020-10-15T17:52:57 Z jc713 Game (IOI13_game) C++17
100 / 100
 4078 ms 50608 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>; 
using vpd = vector<pd>;

#define tcT template<class T
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

// helper funcs
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }

#define tcTU tcT, class U
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
	auto it = t.find(u); assert(it != end(t));
	t.erase(u); } // element that doesn't exist from (multi)set

// INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(vector<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }

tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(vector<T>& x) { trav(a,x) re(a); }
tcT, size_t SZ> void re(AR<T,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
tcT> str ts(complex<T> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

// OUTPUT
tcT> void pr(T x) { cout << ts(x); }
tcTUU> void pr(const T& t, const U&... u) { 
	pr(t); pr(u...); }
void ps() { pr("\n"); } // print w/ spaces
tcTUU> void ps(const T& t, const U&... u) { 
	pr(t); if (sizeof...(u)) pr(" "); ps(u...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

typedef struct tnode* pt;
struct tnode {
	int pri, pos; pt c[2]; ll val, sum;
	tnode (int _pos, ll _val) {
		pos = _pos;
		pri = rng(); sum = val = _val;
		c[0] = c[1] = NULL;
	}
};
ll getsum(pt x) { return x?x->sum:0; }
pt calc(pt x) {
	pt a = x->c[0], b = x->c[1];
	x->sum = gcd2(x->val,gcd2(getsum(a),getsum(b)));
	return x;
}
pair<pt,pt> split(pt t, int v) { // >= v goes to the right
	if (!t) return {t,t};
	if (t->pos >= v) {
		auto p = split(t->c[0], v); t->c[0] = p.s;
		return {p.f,calc(t)};
	} else {
		auto p = split(t->c[1], v); t->c[1] = p.f;
		return {calc(t),p.s};
	}
}
pt merge(pt l, pt r) { // merge treaps, keys in left < keys in right
	if (!l || !r) return l?:r;
	pt t;
	if (l->pri > r->pri) l->c[1] = merge(l->c[1],r), t = l;
	else r->c[0] = merge(l,r->c[0]), t = r;
	return calc(t);
}
pt ins(pt x, int p, ll v) { // insert v
	auto a = split(x,p), b = split(a.s,p+1);
	return merge(a.f,merge(new tnode(p, v),b.s)); }
ll ql(pt x, int L){
	if(!x) return 0;
	if(x->pos < L)
		return ql(x->c[1], L);
	else
		return gcd2(x->val, gcd2(getsum(x->c[1]), ql(x->c[0], L)));
}
ll qr(pt x, int R){
	if(!x) return 0;
	if(x->pos > R)
		return qr(x->c[0], R);
	else
		return gcd2(x->val, gcd2(getsum(x->c[0]), qr(x->c[1], R)));
}
ll qu(pt x, int L, int R){
	if(!x) return 0;
	if(x->pos < L)
		return qu(x->c[1], L, R);
	if(x->pos > R)
		return qu(x->c[0], L, R);
	return gcd2(x->val, gcd2(ql(x->c[0], L), qr(x->c[1], R)));
}

const int SZ = 1e9+10;
template<class T> struct Node {
	pt treap;
	Node* c[2];
	Node() { c[0] = c[1] = NULL; treap = NULL; }
	void upd(int x, int y, T v, int L = 0, int R = SZ-1) { // add v
		if (L == x && R == x) { treap = ins(treap,y,v); return; }
		int M = (L+R)/2;
		if (x <= M) {
			if (!c[0]) c[0] = new Node();
			c[0]->upd(x,y,v,L,M);
		} else {
			if (!c[1]) c[1] = new Node();
			c[1]->upd(x,y,v,M+1,R);
		}
		ll nxt = 0;
			if(c[0])
		nxt = gcd2(nxt, qu(c[0]->treap, y, y));
		if(c[1])
			nxt = gcd2(nxt, qu(c[1]->treap, y, y));
		treap = ins(treap, y, nxt);
	}
	T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ-1) { // query sum of rectangle
		if (x1 <= L && R <= x2) return qu(treap,y1,y2);
		if (x2 < L || R < x1) return 0;
		int M = (L+R)/2; T res = 0;
		if (c[0]) res = gcd2(res, c[0]->query(x1,x2,y1,y2,L,M));
		if (c[1]) res = gcd2(res, c[1]->query(x1,x2,y1,y2,M+1,R));
		return res;
	}
};

Node<ll> tr = Node<ll>();

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    /* ... */
	tr.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return tr.query(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1196 ms 19580 KB Output is correct
5 Correct 899 ms 23288 KB Output is correct
6 Correct 1541 ms 20728 KB Output is correct
7 Correct 1654 ms 20472 KB Output is correct
8 Correct 820 ms 13304 KB Output is correct
9 Correct 1645 ms 20560 KB Output is correct
10 Correct 1480 ms 20088 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1261 ms 23036 KB Output is correct
13 Correct 1858 ms 20052 KB Output is correct
14 Correct 526 ms 20040 KB Output is correct
15 Correct 1913 ms 20064 KB Output is correct
16 Correct 826 ms 20076 KB Output is correct
17 Correct 1179 ms 13560 KB Output is correct
18 Correct 2497 ms 21576 KB Output is correct
19 Correct 2113 ms 21828 KB Output is correct
20 Correct 2005 ms 21012 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1176 ms 23648 KB Output is correct
13 Correct 899 ms 23292 KB Output is correct
14 Correct 1542 ms 20836 KB Output is correct
15 Correct 1681 ms 20464 KB Output is correct
16 Correct 797 ms 13304 KB Output is correct
17 Correct 1655 ms 20472 KB Output is correct
18 Correct 1478 ms 20216 KB Output is correct
19 Correct 1198 ms 23288 KB Output is correct
20 Correct 1833 ms 19704 KB Output is correct
21 Correct 533 ms 20216 KB Output is correct
22 Correct 1931 ms 20112 KB Output is correct
23 Correct 842 ms 20088 KB Output is correct
24 Correct 1177 ms 13816 KB Output is correct
25 Correct 2563 ms 21732 KB Output is correct
26 Correct 2086 ms 21496 KB Output is correct
27 Correct 1945 ms 20856 KB Output is correct
28 Correct 897 ms 28668 KB Output is correct
29 Correct 1590 ms 32328 KB Output is correct
30 Correct 2455 ms 25676 KB Output is correct
31 Correct 2205 ms 25068 KB Output is correct
32 Correct 542 ms 24660 KB Output is correct
33 Correct 719 ms 24696 KB Output is correct
34 Correct 1669 ms 28024 KB Output is correct
35 Correct 1176 ms 20524 KB Output is correct
36 Correct 2573 ms 28640 KB Output is correct
37 Correct 1978 ms 28936 KB Output is correct
38 Correct 2055 ms 28296 KB Output is correct
39 Correct 1618 ms 24440 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1171 ms 23548 KB Output is correct
13 Correct 884 ms 23320 KB Output is correct
14 Correct 1530 ms 20848 KB Output is correct
15 Correct 1645 ms 20468 KB Output is correct
16 Correct 810 ms 13240 KB Output is correct
17 Correct 1615 ms 20632 KB Output is correct
18 Correct 1493 ms 20088 KB Output is correct
19 Correct 1227 ms 23224 KB Output is correct
20 Correct 1810 ms 19832 KB Output is correct
21 Correct 536 ms 20216 KB Output is correct
22 Correct 1966 ms 20344 KB Output is correct
23 Correct 952 ms 20148 KB Output is correct
24 Correct 1191 ms 13688 KB Output is correct
25 Correct 2572 ms 21516 KB Output is correct
26 Correct 2117 ms 21596 KB Output is correct
27 Correct 1990 ms 21068 KB Output is correct
28 Correct 885 ms 27128 KB Output is correct
29 Correct 1607 ms 30200 KB Output is correct
30 Correct 2387 ms 25616 KB Output is correct
31 Correct 2205 ms 25028 KB Output is correct
32 Correct 524 ms 22264 KB Output is correct
33 Correct 709 ms 22520 KB Output is correct
34 Correct 1395 ms 27884 KB Output is correct
35 Correct 1165 ms 17836 KB Output is correct
36 Correct 2610 ms 25576 KB Output is correct
37 Correct 2024 ms 25804 KB Output is correct
38 Correct 2129 ms 25208 KB Output is correct
39 Correct 1216 ms 47864 KB Output is correct
40 Correct 2910 ms 50296 KB Output is correct
41 Correct 4078 ms 45076 KB Output is correct
42 Correct 3438 ms 43784 KB Output is correct
43 Correct 2248 ms 50608 KB Output is correct
44 Correct 799 ms 37496 KB Output is correct
45 Correct 1656 ms 21240 KB Output is correct
46 Correct 3746 ms 48156 KB Output is correct
47 Correct 3796 ms 47932 KB Output is correct
48 Correct 3684 ms 47620 KB Output is correct
49 Correct 1 ms 384 KB Output is correct