답안 #557794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557794	2022-05-06T03:55:57 Z	Noble_Mushtak	게임 (IOI13_game)	C++14	100 / 100	6362 ms	67056 KB

game

//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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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