oj.uz

Submission #242434

# Submission time Handle Problem Language Result Execution time Memory
242434 2020-06-27T16:27:56 Z Benq Game (IOI13_game) C++14
100 / 100
 3808 ms 63136 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"

typedef struct node* pn;
struct node {
    ll d; pn l,r; int L, R;
    node(ll _d, int _L, int _R) : d(_d), L(_L), R(_R) { l = r = NULL; }
};

typedef struct Node* pN;
struct Node {
    pn 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 = __gcd(a,b); } // OK

void UPD(pi P, int Q, ll K, pn& cur, int L = 0, int R = 1e9) {
    if (!cur) { cur = new node(K,Q,Q); return; } // OK
    //dbg("UPDATE",P,mp(cur->L,cur->R),Q,K,L,R);
    if (cur->L <= Q && Q <= cur->R) {
        if (cur->L == cur->R) { cur->d = K; return; }
        int M = (cur->L+cur->R)/2;
        if (Q <= M) UPD(P,Q,K,cur->l,cur->L,M);
        else UPD(P,Q,K,cur->r,M+1,cur->R);
        cur->d = __gcd(cur->l?cur->l->d:0,cur->r?cur->r->d:0);
        return;
    }
    while (1) {
        int M = (L+R)/2; 
        if ((Q <= M) != (cur->L <= M)) break;
        if (Q <= M) R = M;
        else L = M+1;
    }
    pn x = cur, y = new node(K,Q,Q);
    if (cur->L > Q) swap(x,y);
    int M = (L+R)/2;
    assert(L <= x->L && x->R <= M && M < y->L && y->R <= R);
    cur = new node(__gcd(x->d,y->d),L,R);
    cur->l = x, cur->r = y;
}

ll QUERY(pi P, int Q, int V, pn cur) {
    if (!cur || cur->R < Q || V < cur->L) return 0;
    if (Q <= cur->L && cur->R <= V) {
        // dbg("QUERY",P,mp(cur->L,cur->R),Q,V,cur->d);
        // if (cur->l) dbg("LEF",cur->l->d);
        // if (cur->r) dbg("RIG",cur->r->d,cur->r->L,cur->r->R);
        return cur->d;
    }
    return __gcd(QUERY(P,Q,V,cur->l),QUERY(P,Q,V,cur->r));
}

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 UPD({L,R},Q,K,cur->d);
    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) g = __gcd(g,QUERY({L,R},Q,Q,cur->l->d));
    if (cur->r) g = __gcd(g,QUERY({L,R},Q,Q,cur->r->d));
    //dbg("OKUPDATE",mp(L,R),Q,g);
    UPD({L,R},Q,g,cur->d);
}

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

int P,U,Q,V;

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

long long calculate(int _P, int _Q, int _U, int _V) {
    P = _P, Q = _Q, U = _U, V = _V;
    //dbg("QUERY");
    return query(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 6 ms 512 KB Output is correct
3 Correct 6 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 5 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 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 749 ms 35320 KB Output is correct
5 Correct 530 ms 35516 KB Output is correct
6 Correct 870 ms 32364 KB Output is correct
7 Correct 902 ms 32248 KB Output is correct
8 Correct 535 ms 18684 KB Output is correct
9 Correct 908 ms 32208 KB Output is correct
10 Correct 902 ms 31880 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 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 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 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 848 ms 16760 KB Output is correct
13 Correct 1312 ms 10196 KB Output is correct
14 Correct 340 ms 4344 KB Output is correct
15 Correct 1470 ms 12712 KB Output is correct
16 Correct 396 ms 16760 KB Output is correct
17 Correct 857 ms 12640 KB Output is correct
18 Correct 1688 ms 17108 KB Output is correct
19 Correct 1449 ms 17400 KB Output is correct
20 Correct 1410 ms 16620 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 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 304 KB Output is correct
6 Correct 6 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 6 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 799 ms 35276 KB Output is correct
13 Correct 593 ms 35448 KB Output is correct
14 Correct 867 ms 32376 KB Output is correct
15 Correct 912 ms 32232 KB Output is correct
16 Correct 541 ms 18680 KB Output is correct
17 Correct 883 ms 32376 KB Output is correct
18 Correct 880 ms 31828 KB Output is correct
19 Correct 814 ms 16692 KB Output is correct
20 Correct 1319 ms 10120 KB Output is correct
21 Correct 343 ms 4164 KB Output is correct
22 Correct 1481 ms 12824 KB Output is correct
23 Correct 401 ms 16760 KB Output is correct
24 Correct 845 ms 12692 KB Output is correct
25 Correct 1657 ms 17060 KB Output is correct
26 Correct 1351 ms 17212 KB Output is correct
27 Correct 1416 ms 16504 KB Output is correct
28 Correct 480 ms 30712 KB Output is correct
29 Correct 1378 ms 32320 KB Output is correct
30 Correct 2605 ms 27636 KB Output is correct
31 Correct 2304 ms 21516 KB Output is correct
32 Correct 377 ms 2936 KB Output is correct
33 Correct 508 ms 3576 KB Output is correct
34 Correct 756 ms 29560 KB Output is correct
35 Correct 1081 ms 16448 KB Output is correct
36 Correct 2132 ms 29780 KB Output is correct
37 Correct 1644 ms 29896 KB Output is correct
38 Correct 1750 ms 29348 KB Output is correct
39 Correct 1288 ms 23460 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 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 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 6 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 6 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 723 ms 34552 KB Output is correct
13 Correct 564 ms 34916 KB Output is correct
14 Correct 881 ms 31888 KB Output is correct
15 Correct 1020 ms 31540 KB Output is correct
16 Correct 593 ms 18160 KB Output is correct
17 Correct 965 ms 31568 KB Output is correct
18 Correct 1066 ms 31364 KB Output is correct
19 Correct 843 ms 16152 KB Output is correct
20 Correct 1331 ms 9520 KB Output is correct
21 Correct 363 ms 3616 KB Output is correct
22 Correct 1527 ms 12012 KB Output is correct
23 Correct 392 ms 16352 KB Output is correct
24 Correct 841 ms 12072 KB Output is correct
25 Correct 1922 ms 16640 KB Output is correct
26 Correct 1434 ms 16760 KB Output is correct
27 Correct 1316 ms 15992 KB Output is correct
28 Correct 552 ms 30972 KB Output is correct
29 Correct 1431 ms 32376 KB Output is correct
30 Correct 2662 ms 27788 KB Output is correct
31 Correct 2395 ms 21556 KB Output is correct
32 Correct 379 ms 3064 KB Output is correct
33 Correct 601 ms 3564 KB Output is correct
34 Correct 732 ms 29324 KB Output is correct
35 Correct 1050 ms 16552 KB Output is correct
36 Correct 2220 ms 29524 KB Output is correct
37 Correct 1960 ms 29700 KB Output is correct
38 Correct 1770 ms 29016 KB Output is correct
39 Correct 671 ms 60764 KB Output is correct
40 Correct 2460 ms 63136 KB Output is correct
41 Correct 3751 ms 55912 KB Output is correct
42 Correct 3358 ms 42500 KB Output is correct
43 Correct 1110 ms 60892 KB Output is correct
44 Correct 447 ms 2912 KB Output is correct
45 Correct 1519 ms 23148 KB Output is correct
46 Correct 3808 ms 61168 KB Output is correct
47 Correct 3198 ms 61112 KB Output is correct
48 Correct 3227 ms 60916 KB Output is correct
49 Correct 5 ms 384 KB Output is correct