oj.uz

Submission #1088476

# Submission time Handle Problem Language Result Execution time Memory
1088476 2024-09-14T13:28:41 Z makrav Game (IOI13_game) C++17
100 / 100
 5795 ms 96392 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int ll

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct cell {
    int x, y;
};

bool operator<(cell x, cell y) {
    return (x.y == y.y ? x.x < y.x : x.y < y.y);
}

bool operator==(cell x, cell y) {
    return x.x == y.x && x.y == y.y;
}

bool operator>(cell x, cell y) {
    if (x == y) return false;
    return !(x < y);
}

bool compare(cell x, cell y) {
    return (x.x == y.x ? x.y < y.y : x.x < y.x);
}

bool cmp(pair<cell, int> c1, pair<cell, int> c2) {
	if (c1.first == c2.first) return c1.second < c2.second;
	return compare(c1.first, c2.first);
}

struct segtree {
    int n;
    vector<int> a;
    vector<cell> C;
    vector<int> t;
    segtree() = default;
    segtree(int n_, vector<pair<cell, int>> A) {
        n = n_;
        a.resize(n); C.resize(n);
        for (int i = 0; i < n; i++) {
            C[i] = A[i].first; a[i] = A[i].second;
        }
        t.assign(4 * n, 0);
        build(1, 0, n);
    }  

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    void upd(int v, int tl, int tr, cell &c, int newval) {
        if (tl + 1 == tr) {
            t[v] = newval;
            return;
        }
        int tm = (tl + tr) / 2;
        if (C[tm - 1] < c) upd(v * 2 + 1, tm, tr, c, newval);
        else upd(v * 2, tl, tm, c, newval);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    int get(int v, int tl, int tr, int y1, int y2) {
        if (y1 <= C[tl].y && C[tr - 1].y <= y2) return t[v];
        if (C[tl].y > y2 || C[tr - 1].y < y1) return 0;
        int tm = (tl + tr) / 2;
        return gcd(get(v*2,tl,tm,y1,y2), get(v*2+1,tm,tr,y1,y2));
    }
};

struct merge_sort_tree {
    int n;
    vector<pair<cell, int>> xd;
    vector<segtree> sg;
    vector<vector<pair<cell, int>>> tree;
    merge_sort_tree() = default;
    merge_sort_tree(int n_, vector<pair<cell, int>> &xd_) {
        xd =xd_;
        sort(all(xd), cmp);
        n = n_;
        tree.resize(4 * n);
        sg.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            tree[v] = {xd[tl]};
            sg[v] = segtree(tr - tl, tree[v]);
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        tree[v].resize(tr - tl);
        merge(all(tree[v * 2]), all(tree[v * 2 + 1]), tree[v].begin());
        sg[v] = segtree(tr - tl, tree[v]);
    }

    void update_value(int v, int tl, int tr, cell x, int value) {
        sg[v].upd(1, 0, tr - tl, x, value);
        if (tl + 1 == tr) return;
        int tm = (tl + tr) / 2;
        if (compare(xd[tm - 1].first, x)) update_value(v * 2 + 1, tm, tr, x, value);
        else update_value(v * 2, tl, tm, x, value);
    }

    int getans(int v, int tl, int tr, int xl, int xr, int yl, int yr) {
        if (xl > xd[tr - 1].first.x || xr < xd[tl].first.x) return 0;
        if (xl <= xd[tl].first.x && xd[tr - 1].first.x <= xr) {
            return sg[v].get(1, 0, tr - tl, yl, yr);
        }
        int tm = (tl + tr) / 2;
        return gcd(getans(v * 2, tl, tm, xl, xr, yl, yr), getans(v * 2 + 1, tm, tr, xl, xr, yl, yr));
    }
};

map<cell, int> value, firocc;
const int K = 100;
int curind_query = 0, lol = -1;
vector<cell> ahaha;
merge_sort_tree mst;
int mst_size = 0;

void init(int32_t R, int32_t C) {
    /* ... */
}

void update(int32_t P, int32_t Q, long long kk) {
    curind_query++;
    if (firocc.find({P, Q}) == firocc.end()) {
        firocc[{P, Q}] = curind_query;
    }
    value[{P, Q}] = kk;
    if (curind_query % K == 0) {
        vector<pair<cell, int>> to_mst;
        for (auto &u : value) to_mst.pb(u);
        mst_size = sz(to_mst);
        mst = merge_sort_tree(mst_size, to_mst);
        ahaha.clear();
    } else {
        if (firocc[{P, Q}] <= curind_query - curind_query % K) {
            mst.update_value(1, 0, mst_size, {P, Q}, kk);
        } else {
            ahaha.pb({P, Q});
        }
    }
}

long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
    int ans1 = (mst_size == 0 ? 0 : mst.getans(1, 0, mst_size, P, U, Q, V));
    for (auto &u : ahaha) {
        if (P <= u.x && u.x <= U && Q <= u.y && u.y <= V)
        ans1 = gcd(ans1, value[u]);
    }
    return ans1;
}

#ifdef LOCAL 
    signed main() {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        int r, c, n; cin >> r >> c >> n;
        init(r, c);
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            if (t == 1) {
                int p, q, k; cin >> p >> q >> k; update(p, q, k);
            } else {
                int p, q, u, v; cin >> p >> q >> u >> v;
                cout << calculate(p, q, u, v) << '\n';
            }
        }
    }
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1453 ms 43576 KB Output is correct
5 Correct 1162 ms 44868 KB Output is correct
6 Correct 1108 ms 41928 KB Output is correct
7 Correct 1020 ms 39052 KB Output is correct
8 Correct 421 ms 22480 KB Output is correct
9 Correct 1030 ms 38308 KB Output is correct
10 Correct 1115 ms 38152 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 388 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1773 ms 44040 KB Output is correct
13 Correct 1149 ms 30420 KB Output is correct
14 Correct 193 ms 6540 KB Output is correct
15 Correct 1161 ms 31256 KB Output is correct
16 Correct 924 ms 37728 KB Output is correct
17 Correct 599 ms 22424 KB Output is correct
18 Correct 1319 ms 40368 KB Output is correct
19 Correct 1392 ms 42620 KB Output is correct
20 Correct 1519 ms 42008 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1442 ms 44104 KB Output is correct
13 Correct 1188 ms 44820 KB Output is correct
14 Correct 1158 ms 41820 KB Output is correct
15 Correct 1048 ms 39132 KB Output is correct
16 Correct 410 ms 22580 KB Output is correct
17 Correct 985 ms 38332 KB Output is correct
18 Correct 1113 ms 37936 KB Output is correct
19 Correct 1727 ms 44364 KB Output is correct
20 Correct 1171 ms 30464 KB Output is correct
21 Correct 223 ms 6564 KB Output is correct
22 Correct 1160 ms 31364 KB Output is correct
23 Correct 903 ms 37776 KB Output is correct
24 Correct 590 ms 22388 KB Output is correct
25 Correct 1373 ms 40376 KB Output is correct
26 Correct 1381 ms 42604 KB Output is correct
27 Correct 1472 ms 42152 KB Output is correct
28 Correct 913 ms 47020 KB Output is correct
29 Correct 1674 ms 49824 KB Output is correct
30 Correct 1458 ms 43464 KB Output is correct
31 Correct 1118 ms 35032 KB Output is correct
32 Correct 225 ms 11184 KB Output is correct
33 Correct 298 ms 12208 KB Output is correct
34 Correct 993 ms 40380 KB Output is correct
35 Correct 627 ms 28160 KB Output is correct
36 Correct 1332 ms 44564 KB Output is correct
37 Correct 1328 ms 47668 KB Output is correct
38 Correct 1514 ms 46888 KB Output is correct
39 Correct 1066 ms 38860 KB Output is correct
40 Correct 1 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 424 KB Output is correct
12 Correct 1425 ms 44152 KB Output is correct
13 Correct 1133 ms 44940 KB Output is correct
14 Correct 1096 ms 41932 KB Output is correct
15 Correct 1004 ms 39048 KB Output is correct
16 Correct 416 ms 22600 KB Output is correct
17 Correct 1018 ms 38472 KB Output is correct
18 Correct 1113 ms 38076 KB Output is correct
19 Correct 1718 ms 44264 KB Output is correct
20 Correct 1148 ms 30448 KB Output is correct
21 Correct 205 ms 6572 KB Output is correct
22 Correct 1158 ms 31216 KB Output is correct
23 Correct 961 ms 37928 KB Output is correct
24 Correct 608 ms 22548 KB Output is correct
25 Correct 1319 ms 40580 KB Output is correct
26 Correct 1391 ms 42668 KB Output is correct
27 Correct 1686 ms 42004 KB Output is correct
28 Correct 1117 ms 47104 KB Output is correct
29 Correct 1955 ms 50024 KB Output is correct
30 Correct 1463 ms 43404 KB Output is correct
31 Correct 1140 ms 34984 KB Output is correct
32 Correct 253 ms 11244 KB Output is correct
33 Correct 309 ms 12228 KB Output is correct
34 Correct 997 ms 40396 KB Output is correct
35 Correct 664 ms 28436 KB Output is correct
36 Correct 1377 ms 44528 KB Output is correct
37 Correct 1291 ms 47716 KB Output is correct
38 Correct 1457 ms 46904 KB Output is correct
39 Correct 3563 ms 95312 KB Output is correct
40 Correct 4381 ms 96392 KB Output is correct
41 Correct 3994 ms 92040 KB Output is correct
42 Correct 3211 ms 69712 KB Output is correct
43 Correct 4568 ms 85408 KB Output is correct
44 Correct 393 ms 13396 KB Output is correct
45 Correct 963 ms 39056 KB Output is correct
46 Correct 4611 ms 95252 KB Output is correct
47 Correct 4783 ms 95292 KB Output is correct
48 Correct 5795 ms 95032 KB Output is correct
49 Correct 1 ms 344 KB Output is correct