oj.uz

Submission #242393

# Submission time Handle Problem Language Result Execution time Memory
242393 2020-06-27T15:06:13 Z Benq Game (IOI13_game) C++14
100 / 100
 3626 ms 67828 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#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 

#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; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
constexpr int pct(int x) { return __builtin_popcount(x); } 
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
template<class T> void remDup(vector<T>& v) { 
    sort(all(v)); v.erase(unique(all(v)),end(v)); }

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> 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); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> 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; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

#include "game.h"

/**
 * Description: Easy BBST. Use split and merge to implement insert and delete.
 * Time: O(\log N)
 * Source: https://cp-algorithms.com/data_structures/treap.html + others. Also consider
 	* https://codeforces.com/contest/1340/submission/77861280 (no pointers -> faster)
 	* https://codeforces.com/contest/1340/submission/77852254 (shared_ptr -> destroyed when nothing refers to it)
 * Verification: http://www.spoj.com/problems/ORDERSET/
 */

typedef struct tnode* pt;
struct tnode {
	int pri; pt c[2]; // essential
	int pos; ll val, sum;
	tnode (int _pos, ll _val) {
		pri = rng(); c[0] = c[1] = NULL;
		pos = _pos, val = sum = _val;
	}
};
ll getSum(pt x) { return x?x->sum:0; } // OK
ll co(ll a, ll b) { return __gcd(a,b); } // OK
pt calc(pt x) {
	x->sum = co(x->val,co(getSum(x->c[0]),getSum(x->c[1])));
	return x; }
// void tour(pt x, vi& v) { // print values of nodes, 
// 	if (!x) return; // inorder traversal
// 	tour(x->c[0],v); v.pb(x->val); tour(x->c[1],v);
// }
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 pos, ll val) { // insert v
	auto a = split(x,pos), b = split(a.s,pos+1);
	//dbg("SPLIT");
	return merge(a.f,merge(new tnode(pos,val),b.s)); }
void INS(pt& x, int pos, ll val) { 
	//dbg("INS",pos,val);
	x = ins(x,pos,val); 
	//dbg("DONEINS");
}
ll searchLef(pt p, int L) {
	if (!p) return 0;
	if (p->pos < L) return searchLef(p->c[1],L);
	return co(p->val,co(searchLef(p->c[0],L),getSum(p->c[1])));
}
ll searchRig(pt p, int R) {
	if (!p) return 0;
	if (p->pos > R) return searchRig(p->c[0],R);
	return co(p->val,co(searchRig(p->c[1],R),getSum(p->c[0])));
}
ll search(pt p, int L, int R) {
	if (!p) return 0;
	if (p->pos < L) return search(p->c[1],L,R);
	if (p->pos > R) return search(p->c[0],L,R);
	return co(p->val,co(searchLef(p->c[0],L),searchRig(p->c[1],R)));
}

typedef struct Node* pN;
struct Node {
    pt d; pN l,r;
    Node() { d = NULL; l = r = NULL; }
};

pN root = NULL;

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

void tri(ll& a, ll b) { a = co(a,b); } // OK

void upd(int P, int Q, ll K, pN& cur, int L = 0, int R = 1e9) {
    if (!cur) cur = new Node();
    if (L == R) return INS(cur->d,Q,K);
    int M = (L+R)/2;
    if (P <= M) upd(P,Q,K,cur->l,L,M);
    else upd(P,Q,K,cur->r,M+1,R);
    ll g = 0; 
    if (cur->l) tri(g,search(cur->l->d,Q,Q));
    if (cur->r) tri(g,search(cur->r->d,Q,Q));
    //dbg("OOPS",g);
    INS(cur->d,Q,g);
}

void update(int P, int Q, long long K) { 
    //dbg("UPDATE");
    upd(P,Q,K,root); }

ll query(int P, int U, int Q, int V, pN cur, int L = 0, int R = 1e9) {
    if (!cur || R < P || U < L) return 0; // OK
    if (P <= L && R <= U) return search(cur->d,Q,V);
    int M = (L+R)/2;
    return __gcd(query(P,U,Q,V,cur->l,L,M),query(P,U,Q,V,cur->r,M+1,R));
}

long long calculate(int P, int Q, int U, int V) {
    //dbg("QUERY");
    return query(P,U,Q,V,root);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'void setIn(std::__cxx11::string)':
game.cpp:130:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void setOut(std::__cxx11::string)':
game.cpp:131:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1201 ms 25384 KB Output is correct
5 Correct 957 ms 25592 KB Output is correct
6 Correct 1562 ms 22240 KB Output is correct
7 Correct 1582 ms 22008 KB Output is correct
8 Correct 790 ms 12664 KB Output is correct
9 Correct 1686 ms 22140 KB Output is correct
10 Correct 1441 ms 21808 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1158 ms 25384 KB Output is correct
13 Correct 1631 ms 22084 KB Output is correct
14 Correct 522 ms 21788 KB Output is correct
15 Correct 1708 ms 22020 KB Output is correct
16 Correct 808 ms 22008 KB Output is correct
17 Correct 1407 ms 12408 KB Output is correct
18 Correct 2657 ms 22648 KB Output is correct
19 Correct 2156 ms 22648 KB Output is correct
20 Correct 1844 ms 21988 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1204 ms 25464 KB Output is correct
13 Correct 887 ms 25464 KB Output is correct
14 Correct 1513 ms 22648 KB Output is correct
15 Correct 1694 ms 22008 KB Output is correct
16 Correct 819 ms 12792 KB Output is correct
17 Correct 1652 ms 22292 KB Output is correct
18 Correct 1584 ms 21624 KB Output is correct
19 Correct 1182 ms 25256 KB Output is correct
20 Correct 1663 ms 22044 KB Output is correct
21 Correct 528 ms 21880 KB Output is correct
22 Correct 1804 ms 22136 KB Output is correct
23 Correct 784 ms 22136 KB Output is correct
24 Correct 1180 ms 12792 KB Output is correct
25 Correct 2386 ms 22492 KB Output is correct
26 Correct 2137 ms 22640 KB Output is correct
27 Correct 1969 ms 22076 KB Output is correct
28 Correct 836 ms 32472 KB Output is correct
29 Correct 1467 ms 39132 KB Output is correct
30 Correct 2225 ms 30544 KB Output is correct
31 Correct 1968 ms 29816 KB Output is correct
32 Correct 543 ms 29432 KB Output is correct
33 Correct 702 ms 29560 KB Output is correct
34 Correct 1369 ms 32760 KB Output is correct
35 Correct 1126 ms 23928 KB Output is correct
36 Correct 2354 ms 37048 KB Output is correct
37 Correct 1930 ms 37112 KB Output is correct
38 Correct 1942 ms 36688 KB Output is correct
39 Correct 1514 ms 31096 KB Output is correct
40 Correct 5 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 664 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1173 ms 24752 KB Output is correct
13 Correct 966 ms 24824 KB Output is correct
14 Correct 1513 ms 21760 KB Output is correct
15 Correct 1706 ms 21496 KB Output is correct
16 Correct 813 ms 12152 KB Output is correct
17 Correct 1621 ms 21628 KB Output is correct
18 Correct 1474 ms 21112 KB Output is correct
19 Correct 1162 ms 24696 KB Output is correct
20 Correct 1642 ms 21288 KB Output is correct
21 Correct 510 ms 21112 KB Output is correct
22 Correct 1749 ms 21440 KB Output is correct
23 Correct 995 ms 21344 KB Output is correct
24 Correct 1201 ms 11824 KB Output is correct
25 Correct 2245 ms 21624 KB Output is correct
26 Correct 2414 ms 22012 KB Output is correct
27 Correct 1903 ms 21372 KB Output is correct
28 Correct 825 ms 32248 KB Output is correct
29 Correct 1462 ms 39180 KB Output is correct
30 Correct 2264 ms 30288 KB Output is correct
31 Correct 1977 ms 29944 KB Output is correct
32 Correct 548 ms 29432 KB Output is correct
33 Correct 686 ms 29560 KB Output is correct
34 Correct 1537 ms 33016 KB Output is correct
35 Correct 1134 ms 24056 KB Output is correct
36 Correct 2469 ms 37112 KB Output is correct
37 Correct 1967 ms 37496 KB Output is correct
38 Correct 1899 ms 36620 KB Output is correct
39 Correct 1149 ms 65920 KB Output is correct
40 Correct 2611 ms 67828 KB Output is correct
41 Correct 3488 ms 57412 KB Output is correct
42 Correct 3188 ms 55972 KB Output is correct
43 Correct 2060 ms 62712 KB Output is correct
44 Correct 759 ms 53112 KB Output is correct
45 Correct 1499 ms 30940 KB Output is correct
46 Correct 3496 ms 66808 KB Output is correct
47 Correct 3626 ms 66552 KB Output is correct
48 Correct 3464 ms 66292 KB Output is correct
49 Correct 5 ms 384 KB Output is correct