oj.uz

Submission #168457

# Submission time Handle Problem Language Result Execution time Memory
168457 2019-12-13T06:58:48 Z tri Game (IOI13_game) C++14
80 / 100
 9181 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 20000000;

int R, C;

ll lC[MAXN], rC[MAXN], tr[MAXN];
// let tr[0] = 0 to represent all blank ranges
int nN = 2;

inline ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void update1(int i, int l, int r, int x, ll v) {
//    ps("update1", i, l, r, x, v);
    if (l == r) {
        tr[i] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        if (lC[i] == 0) lC[i] = nN++;
        update1(lC[i], l, mid, x, v);
    } else {
        if (rC[i] == 0) rC[i] = nN++;
        update1(rC[i], mid + 1, r, x, v);
    }
    tr[i] = gcd(tr[lC[i]], tr[rC[i]]);
}

ll query1(int i, int l, int r, int s, int e) {
    if (i == 0) return 0; // range all 0's
    if (e < l || r < s) {
        return 0;
    }

    if (s <= l && r <= e) {
        return tr[i];
    }

    int mid = (l + r) / 2;
    return gcd(query1(lC[i], l, mid, s, e), query1(rC[i], mid + 1, r, s, e));
}

ll update2(int i, int l, int r, int x, int y, ll v) {
    if (tr[i] == 0) tr[i] = nN++;
    int cT = tr[i];
//    ps();

    if (l == r) {
        update1(cT, 0, 1e9, y, v);
        return v;
    }

    int mid = (l + r) / 2;

    ll lRes = 0, rRes = 0;
    if (x <= mid) {
        if (lC[i] == 0) lC[i] = nN++;
        lRes = update2(lC[i], l, mid, x, y, v);
        rRes = query1(tr[rC[i]], 0, 1e9, y, y);
    } else {
        if (rC[i] == 0) rC[i] = nN++;
        lRes = query1(tr[lC[i]], 0, 1e9, y, y);
        rRes = update2(rC[i], mid + 1, r, x, y, v);
    }

    ll nVal = gcd(lRes, rRes);
//    ps("update2", i, l, r, x, y, v);
//    ps(nVal);
    update1(cT, 0, 1e9, y, nVal);
    return nVal;
}


ll query2(int i, int l, int r, int s, int e, int s2, int e2) {
    if (i == 0 || tr[i] == 0) return 0;
    if (e < l || r < s) {
        return 0;
    }

    if (s <= l && r <= e) {
        return query1(tr[i], 0, 1e9, s2, e2);
    }

    int mid = (l + r) / 2;
    return gcd(query2(lC[i], l, mid, s, e, s2, e2), query2(rC[i], mid + 1, r, s, e, s2, e2));
}

void init(int iR, int iC) {
    R = iR, C = iC;
}

void update(int P, int Q, ll K) {
//    ps("updating", P, Q, K);

    update2(1, 0, 1e9, P, Q, K);
//    ps(K);
//    if (K == 12) {
//        ps("request");
//        ps(query2(1, 0, 1e9, 0, 1, 0, 2));
//        ps(query2(1, 0, 1e9, 0, 1, 0, 1));
//        ps(query2(1, 0, 1e9, 0, 1, 1, 2));
//    }
//    DEBUG = true;
}

ll calculate(int P, int Q, int U, int V) {
    ll ans = query2(1, 0, 1e9, P, U, Q, V);
    return ans;
}

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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1257 ms 43608 KB Output is correct
5 Correct 952 ms 43108 KB Output is correct
6 Correct 1552 ms 40748 KB Output is correct
7 Correct 1577 ms 40556 KB Output is correct
8 Correct 1036 ms 26504 KB Output is correct
9 Correct 1593 ms 40748 KB Output is correct
10 Correct 1419 ms 40344 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1875 ms 19464 KB Output is correct
13 Correct 3057 ms 10912 KB Output is correct
14 Correct 836 ms 5880 KB Output is correct
15 Correct 3466 ms 14968 KB Output is correct
16 Correct 846 ms 22100 KB Output is correct
17 Correct 2055 ms 17564 KB Output is correct
18 Correct 3254 ms 23552 KB Output is correct
19 Correct 2816 ms 23716 KB Output is correct
20 Correct 2759 ms 23224 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 636 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1278 ms 43384 KB Output is correct
13 Correct 947 ms 43076 KB Output is correct
14 Correct 1545 ms 40792 KB Output is correct
15 Correct 1568 ms 40568 KB Output is correct
16 Correct 1006 ms 26456 KB Output is correct
17 Correct 1712 ms 40952 KB Output is correct
18 Correct 1347 ms 40288 KB Output is correct
19 Correct 1930 ms 19432 KB Output is correct
20 Correct 3024 ms 11044 KB Output is correct
21 Correct 836 ms 6136 KB Output is correct
22 Correct 3483 ms 15000 KB Output is correct
23 Correct 825 ms 22220 KB Output is correct
24 Correct 2056 ms 17768 KB Output is correct
25 Correct 3207 ms 23592 KB Output is correct
26 Correct 3218 ms 23824 KB Output is correct
27 Correct 2503 ms 23268 KB Output is correct
28 Correct 1108 ms 199644 KB Output is correct
29 Correct 2797 ms 220388 KB Output is correct
30 Correct 9181 ms 160020 KB Output is correct
31 Correct 8752 ms 124012 KB Output is correct
32 Correct 856 ms 10616 KB Output is correct
33 Correct 1110 ms 12380 KB Output is correct
34 Correct 1667 ms 214224 KB Output is correct
35 Correct 2147 ms 115148 KB Output is correct
36 Correct 4107 ms 218456 KB Output is correct
37 Correct 3296 ms 218344 KB Output is correct
38 Correct 3215 ms 217844 KB Output is correct
39 Correct 2775 ms 169932 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1262 ms 43492 KB Output is correct
13 Correct 944 ms 43160 KB Output is correct
14 Correct 1624 ms 40780 KB Output is correct
15 Correct 1592 ms 40484 KB Output is correct
16 Correct 998 ms 26632 KB Output is correct
17 Correct 1593 ms 40916 KB Output is correct
18 Correct 1444 ms 40284 KB Output is correct
19 Correct 1957 ms 19224 KB Output is correct
20 Correct 3033 ms 11016 KB Output is correct
21 Correct 848 ms 6008 KB Output is correct
22 Correct 3458 ms 14912 KB Output is correct
23 Correct 831 ms 22336 KB Output is correct
24 Correct 2016 ms 17788 KB Output is correct
25 Correct 3179 ms 23716 KB Output is correct
26 Correct 3031 ms 23736 KB Output is correct
27 Correct 2546 ms 23120 KB Output is correct
28 Correct 1132 ms 199612 KB Output is correct
29 Correct 2726 ms 220480 KB Output is correct
30 Correct 9153 ms 160076 KB Output is correct
31 Correct 8696 ms 124024 KB Output is correct
32 Correct 854 ms 10488 KB Output is correct
33 Correct 1109 ms 12296 KB Output is correct
34 Correct 1643 ms 214176 KB Output is correct
35 Correct 2228 ms 115136 KB Output is correct
36 Correct 4024 ms 218432 KB Output is correct
37 Correct 3300 ms 218528 KB Output is correct
38 Correct 3110 ms 217876 KB Output is correct
39 Runtime error 932 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -