oj.uz

Submission #557794

# Submission time Handle Problem Language Result Execution time Memory
557794 2022-05-06T03:55:57 Z Noble_Mushtak Game (IOI13_game) C++14
100 / 100
 6362 ms 67056 KB 
//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

#ifdef __cplusplus
extern "C" {
#endif

void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);

#ifdef __cplusplus
}
#endif

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

struct node;
struct treap { node *root; treap(node *r = nullptr) : root(r) {} };
std::mt19937 irand(std::random_device{}()); //std::mt19937_64 for 64-bit priority
struct node {
    num pri;
    num val, assoc, total;
    int sze;
    treap left, right;
    node() {}
    node(num x, num a) : pri(irand()), val(x), assoc(a), total(a), sze(1), left(), right() { }
};
node* newTNode(num val, num a) { return new node(val, a); }
num total(treap t) { return t.root ? t.root->total : 0; }
int sze(treap t) { return t.root ? t.root->sze : 0; }
static inline void push(treap t) {}
void update(treap t) {
    if (!t.root) return;
    treap &left = t.root->left, &right = t.root->right;
    push(left), push(right);
    t.root->sze = sze(left)+sze(right)+1;
    t.root->total = __gcd(t.root->assoc, __gcd(total(t.root->left), total(t.root->right)));
}
treap merge(treap left, treap right) {
    push(left), push(right);
    treap n;
    if (!left.root || !right.root) n = left.root ? left : right;
    else if (left.root->pri > right.root->pri) left.root->right = merge(left.root->right, right), n = left;
    else right.root->left = merge(left, right.root->left), n = right;
    update(n);
    return n;
}
//pos: pos elements in left treap
//val: all elements in < val in left treap, all elements >= val in right treap
std::pair<treap, treap> splitByVal(treap t, num val) {
    if (!t.root) return {{}, {}};
    push(t); //Add update(t) if updates affect size of left/right nodes
    treap &left = t.root->left, &right = t.root->right;
    if (t.root->val < val) {
        auto pr = splitByVal(right, val);
        t.root->right = pr.first;
        update(t);
        return {{t.root}, pr.second};
    }
    auto pr = splitByVal(left, val);
    t.root->left = pr.second;
    update(t);
    return {pr.first, {t.root}};
}

struct segtree2d {
    int root = 1;
    int sze = 1;
    int mnX, mxX, mnY, mxY;
    vector<int> lc, rc;
    vector<treap> st;
    segtree2d() {}
    segtree2d(int R, int C) : mnX(0), mxX(R-1), mnY(0), mxY(C-1), lc(700000), rc(700000), st(700000) {}
    int newNode() {
        ++sze;
        while (sze >= sz(lc)) {
            lc.push_back(0);
            rc.push_back(0);
            st.push_back({});
        }
        return sze;
    }
    num getVal(int n, int y1, int y2) {
        if (n == 0) return 0;
        treap l, r, rl, rr;
        tie(l, r) = splitByVal(st[n], y1);
        tie(rl, rr) = splitByVal(r, y2+1);
        num ans = total(rl);
        st[n] = merge(l, merge(rl, rr));
        return ans;
    }
    num queryH(int x1, int y1, int x2, int y2, int lo, int hi, int &node) {
        if ((x2 < lo) || (hi < x1) || (node == 0)) return 0;
        if ((x1 <= lo) && (hi <= x2)) return getVal(node, y1, y2);
        int mid = (lo+hi)/2;
        return __gcd(queryH(x1, y1, x2, y2, lo, mid, lc[node]), queryH(x1, y1, x2, y2, mid+1, hi, rc[node]));
    }
    num query(int x1, int y1, int x2, int y2) {
        return queryH(x1, y1, x2, y2, mnX, mxX, root);
    }
    void updateH(int x, int y, num newV, int lo, int hi, int &node) {
        if ((x < lo) || (hi < x)) return;
        if (node == 0) node = newNode();
        if (lo != hi) {
            int mid = (lo+hi)/2;
            updateH(x, y, newV, lo, mid, lc[node]);
            updateH(x, y, newV, mid+1, hi, rc[node]);
            newV = __gcd(getVal(lc[node], y, y), getVal(rc[node], y, y));
        }
        treap l, r, rl, rr;
        tie(l, r) = splitByVal(st[node], y);
        tie(rl, rr) = splitByVal(r, y+1);
        st[node] = merge(l, merge(treap(newTNode(y, newV)), rr));
    }
    void update(int x, int y, num newV) {
        return updateH(x, y, newV, mnX, mxX, root);
    }
};

segtree2d data;

void init(int R, int C) {
    data = segtree2d(R, C);
}

void update(int P, int Q, long long V) {
    data.update(P, Q, V);
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11220 KB Output is correct
3 Correct 6 ms 11228 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Correct 5 ms 11176 KB Output is correct
8 Correct 5 ms 11252 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Correct 5 ms 11180 KB Output is correct
11 Correct 5 ms 11220 KB Output is correct
12 Correct 6 ms 11220 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11200 KB Output is correct
2 Correct 6 ms 11180 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 836 ms 19060 KB Output is correct
5 Correct 387 ms 19148 KB Output is correct
6 Correct 1108 ms 15924 KB Output is correct
7 Correct 1229 ms 15892 KB Output is correct
8 Correct 812 ms 15160 KB Output is correct
9 Correct 1180 ms 16052 KB Output is correct
10 Correct 1026 ms 15452 KB Output is correct
11 Correct 5 ms 11220 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11220 KB Output is correct
3 Correct 6 ms 11312 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11312 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Correct 6 ms 11188 KB Output is correct
11 Correct 5 ms 11220 KB Output is correct
12 Correct 1297 ms 23180 KB Output is correct
13 Correct 2716 ms 19768 KB Output is correct
14 Correct 425 ms 20120 KB Output is correct
15 Correct 2973 ms 20368 KB Output is correct
16 Correct 413 ms 20288 KB Output is correct
17 Correct 1703 ms 17060 KB Output is correct
18 Correct 3086 ms 20816 KB Output is correct
19 Correct 2570 ms 21076 KB Output is correct
20 Correct 2411 ms 20332 KB Output is correct
21 Correct 5 ms 11220 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Correct 6 ms 11268 KB Output is correct
11 Correct 6 ms 11220 KB Output is correct
12 Correct 846 ms 18936 KB Output is correct
13 Correct 376 ms 19260 KB Output is correct
14 Correct 1088 ms 16028 KB Output is correct
15 Correct 1233 ms 15744 KB Output is correct
16 Correct 827 ms 14996 KB Output is correct
17 Correct 1196 ms 15788 KB Output is correct
18 Correct 1024 ms 15812 KB Output is correct
19 Correct 1276 ms 23076 KB Output is correct
20 Correct 2631 ms 19808 KB Output is correct
21 Correct 429 ms 20140 KB Output is correct
22 Correct 2863 ms 20340 KB Output is correct
23 Correct 434 ms 20332 KB Output is correct
24 Correct 1723 ms 16968 KB Output is correct
25 Correct 3147 ms 20644 KB Output is correct
26 Correct 2572 ms 20864 KB Output is correct
27 Correct 2382 ms 20260 KB Output is correct
28 Correct 1074 ms 32072 KB Output is correct
29 Correct 2016 ms 35100 KB Output is correct
30 Correct 3728 ms 32156 KB Output is correct
31 Correct 3269 ms 32160 KB Output is correct
32 Correct 617 ms 32108 KB Output is correct
33 Correct 901 ms 32244 KB Output is correct
34 Correct 609 ms 32284 KB Output is correct
35 Correct 2023 ms 22988 KB Output is correct
36 Correct 4062 ms 32680 KB Output is correct
37 Correct 3322 ms 32752 KB Output is correct
38 Correct 3392 ms 32144 KB Output is correct
39 Correct 2770 ms 28104 KB Output is correct
40 Correct 5 ms 11220 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 6 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Correct 5 ms 11236 KB Output is correct
11 Correct 5 ms 11220 KB Output is correct
12 Correct 817 ms 18904 KB Output is correct
13 Correct 389 ms 19160 KB Output is correct
14 Correct 1159 ms 15908 KB Output is correct
15 Correct 1234 ms 15716 KB Output is correct
16 Correct 841 ms 15052 KB Output is correct
17 Correct 1206 ms 15908 KB Output is correct
18 Correct 1063 ms 15564 KB Output is correct
19 Correct 1290 ms 23252 KB Output is correct
20 Correct 2794 ms 19832 KB Output is correct
21 Correct 430 ms 20112 KB Output is correct
22 Correct 3012 ms 20452 KB Output is correct
23 Correct 411 ms 20404 KB Output is correct
24 Correct 1715 ms 17020 KB Output is correct
25 Correct 3144 ms 20792 KB Output is correct
26 Correct 2560 ms 20948 KB Output is correct
27 Correct 2447 ms 20248 KB Output is correct
28 Correct 1097 ms 31928 KB Output is correct
29 Correct 2039 ms 35196 KB Output is correct
30 Correct 3668 ms 31868 KB Output is correct
31 Correct 3277 ms 32532 KB Output is correct
32 Correct 621 ms 31964 KB Output is correct
33 Correct 944 ms 32004 KB Output is correct
34 Correct 611 ms 32000 KB Output is correct
35 Correct 2149 ms 22772 KB Output is correct
36 Correct 4164 ms 32364 KB Output is correct
37 Correct 3220 ms 32804 KB Output is correct
38 Correct 3256 ms 31956 KB Output is correct
39 Correct 1568 ms 56640 KB Output is correct
40 Correct 3462 ms 67056 KB Output is correct
41 Correct 5630 ms 61788 KB Output is correct
42 Correct 5062 ms 61696 KB Output is correct
43 Correct 1216 ms 61936 KB Output is correct
44 Correct 931 ms 63940 KB Output is correct
45 Correct 2729 ms 37444 KB Output is correct
46 Correct 5878 ms 65904 KB Output is correct
47 Correct 6362 ms 65892 KB Output is correct
48 Correct 6062 ms 65420 KB Output is correct
49 Correct 7 ms 11220 KB Output is correct