oj.uz

Submission #281965

# Submission time Handle Problem Language Result Execution time Memory
281965 2020-08-23T16:31:17 Z Benq Game (IOI13_game) C++14
80 / 100
 5628 ms 256000 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 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 = 0; pn l,r;
//     node() { l = r = NULL; }
// };

const int AA = 12e6;
int aa;
ll d[AA]; int lq[AA], rq[AA];

// typedef struct Node* pN;
// struct Node {
//     pn d; pN l,r;
//     Node() { d = NULL, l = r = NULL; }
// };
 
const int BB = 400000;
int bb;
int D[BB], LQ[BB], RQ[BB];
int root = 0;
 
void init(int R, int C) {
    /* ... */
}
 
void tri(ll& a, ll b) { a = __gcd(a,b); }
 
void UPD(int Q, ll K, int& cur, int L = 0, int R = 1e9) {
    // dbg("UPD",Q,K,L,R);
    if (!cur) cur = ++aa;
    if (L == R) { d[cur] = K; return; }
    int M = (L+R)/2;
    if (Q <= M) UPD(Q,K,lq[cur],L,M);
    else UPD(Q,K,rq[cur],M+1,R);
    d[cur] = 0;
    if (lq[cur]) tri(d[cur],d[lq[cur]]);
    if (rq[cur]) tri(d[cur],d[rq[cur]]);
}
 
void pull(int Q, int& cur, int l, int r, int L = 0, int R = 1e9) {
    if (!cur) cur = ++aa;
    d[cur] = 0;
    if (l) tri(d[cur],d[l]);
    if (r) tri(d[cur],d[r]);
    if (L == R) return;
    int M = (L+R)/2;
    if (Q <= M) pull(Q,lq[cur],lq[l],lq[r],L,M);
    else pull(Q,rq[cur],rq[l],rq[r],M+1,R);
}
 
void upd(int P, int Q, ll K, int& cur, int L = 0, int R = 1e9) {
    if (!cur) cur = ++bb;
    if (L == R) return UPD(Q,K,D[cur]);
    int M = (L+R)/2;
    if (P <= M) upd(P,Q,K,LQ[cur],L,M);
    else upd(P,Q,K,RQ[cur],M+1,R);
    pull(Q,D[cur],D[LQ[cur]],D[RQ[cur]]);
}
 
void update(int P, int Q, long long K) { 
    dbg("UPDATE");
    upd(P,Q,K,root); }
 
ll QUERY(int Q, int V, int cur, int L = 0, int R = 1e9) {
    if (!cur || R < Q || V < L) return 0;
    if (Q <= L && R <= V) return d[cur];
    int M = (L+R)/2;
    return __gcd(QUERY(Q,V,lq[cur],L,M),QUERY(Q,V,rq[cur],M+1,R));
}
 
ll query(int P, int U, int Q, int V, int cur, int L = 0, int R = 1e9) {
    if (!cur || R < P || U < L) return 0;
    if (P <= L && R <= U) return QUERY(Q,V,D[cur]);
    int M = (L+R)/2;
    return __gcd(query(P,U,Q,V,LQ[cur],L,M),query(P,U,Q,V,RQ[cur],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]
   18 |  int res;
      |      ^~~
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:125:18: warning: statement has no effect [-Wunused-value]
  125 | #define dbg(...) 0
      |                  ^
game.cpp:202:5: note: in expansion of macro 'dbg'
  202 |     dbg("UPDATE");
      |     ^~~
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:125:18: warning: statement has no effect [-Wunused-value]
  125 | #define dbg(...) 0
      |                  ^
game.cpp:220:5: note: in expansion of macro 'dbg'
  220 |     dbg("QUERY");
      |     ^~~
game.cpp: In function 'void setIn(std::string)':
game.cpp:129:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  129 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void setOut(std::string)':
game.cpp:130:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  130 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 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 985 ms 29272 KB Output is correct
5 Correct 803 ms 29312 KB Output is correct
6 Correct 961 ms 26232 KB Output is correct
7 Correct 1079 ms 25976 KB Output is correct
8 Correct 685 ms 17144 KB Output is correct
9 Correct 999 ms 26196 KB Output is correct
10 Correct 979 ms 25572 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 416 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 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 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1612 ms 13560 KB Output is correct
13 Correct 2192 ms 6672 KB Output is correct
14 Correct 702 ms 2936 KB Output is correct
15 Correct 2464 ms 9208 KB Output is correct
16 Correct 713 ms 14200 KB Output is correct
17 Correct 1464 ms 10932 KB Output is correct
18 Correct 2548 ms 14380 KB Output is correct
19 Correct 2090 ms 14584 KB Output is correct
20 Correct 1944 ms 14196 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 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 2 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 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 969 ms 28920 KB Output is correct
13 Correct 770 ms 28924 KB Output is correct
14 Correct 949 ms 25976 KB Output is correct
15 Correct 998 ms 25696 KB Output is correct
16 Correct 690 ms 17016 KB Output is correct
17 Correct 973 ms 25976 KB Output is correct
18 Correct 987 ms 25560 KB Output is correct
19 Correct 1675 ms 13004 KB Output is correct
20 Correct 2156 ms 6624 KB Output is correct
21 Correct 711 ms 2852 KB Output is correct
22 Correct 2438 ms 8876 KB Output is correct
23 Correct 687 ms 13816 KB Output is correct
24 Correct 1485 ms 10572 KB Output is correct
25 Correct 2444 ms 13944 KB Output is correct
26 Correct 2085 ms 14200 KB Output is correct
27 Correct 1890 ms 13688 KB Output is correct
28 Correct 849 ms 127608 KB Output is correct
29 Correct 2373 ms 142728 KB Output is correct
30 Correct 5628 ms 103448 KB Output is correct
31 Correct 5194 ms 79480 KB Output is correct
32 Correct 601 ms 2552 KB Output is correct
33 Correct 787 ms 3912 KB Output is correct
34 Correct 1073 ms 139316 KB Output is correct
35 Correct 1694 ms 72344 KB Output is correct
36 Correct 3246 ms 140124 KB Output is correct
37 Correct 2593 ms 139884 KB Output is correct
38 Correct 2551 ms 138848 KB Output is correct
39 Correct 2169 ms 107280 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 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 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 974 ms 28212 KB Output is correct
13 Correct 761 ms 28448 KB Output is correct
14 Correct 902 ms 25124 KB Output is correct
15 Correct 983 ms 25080 KB Output is correct
16 Correct 702 ms 16248 KB Output is correct
17 Correct 987 ms 25056 KB Output is correct
18 Correct 974 ms 24728 KB Output is correct
19 Correct 1597 ms 12108 KB Output is correct
20 Correct 2109 ms 5524 KB Output is correct
21 Correct 694 ms 1524 KB Output is correct
22 Correct 2414 ms 7800 KB Output is correct
23 Correct 693 ms 12672 KB Output is correct
24 Correct 1469 ms 9328 KB Output is correct
25 Correct 2431 ms 13232 KB Output is correct
26 Correct 1982 ms 13156 KB Output is correct
27 Correct 2043 ms 12764 KB Output is correct
28 Correct 878 ms 125560 KB Output is correct
29 Correct 2338 ms 141124 KB Output is correct
30 Correct 5342 ms 101900 KB Output is correct
31 Correct 5101 ms 78072 KB Output is correct
32 Correct 600 ms 1064 KB Output is correct
33 Correct 770 ms 2552 KB Output is correct
34 Correct 1066 ms 137848 KB Output is correct
35 Correct 1685 ms 70356 KB Output is correct
36 Correct 3344 ms 138248 KB Output is correct
37 Correct 2575 ms 138412 KB Output is correct
38 Correct 2550 ms 137904 KB Output is correct
39 Runtime error 988 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -