oj.uz

Submission #1081963

# Submission time Handle Problem Language Result Execution time Memory
1081963 2024-08-30T13:23:37 Z TheQuantiX Game (IOI13_game) C++17
63 / 100
 2688 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;

struct segtree1d {
    vector<ll> tr;
    vector<ll> pl, pr;

    segtree1d() {
        tr.assign(1, 0);
        pl.assign(1, -1);
        pr.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 2; i++) {
            tr.push_back(0);
            pl.push_back(-1);
            pr.push_back(-1);
        }
        pl[x] = tr.size() - 2;
        pr[x] = tr.size() - 1;
    }

    void update(ll x, ll l, ll r, ll idx, ll val) {
        // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << idx << ' ' << val << '\n';
        if (l == r) {
            tr[x] = val;
            return;
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        if (idx <= mid) {
            update(pl[x], l, mid, idx, val);
        }
        else {
            update(pr[x], mid + 1, r, idx, val);
        }
        tr[x] = gcd(tr[pl[x]], tr[pr[x]]);
    }

    ll query(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return 0;
        }
        if (r < L) {
            return 0;
        }
        if (R < l) {
            return 0;
        }
        if (R < L) {
            return 0;
        }
        if (L <= l && r <= R) {
            return tr[x];
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        return gcd(query(pl[x], l, mid, L, R), query(pr[x], mid + 1, r, L, R));
    }
};

struct segtree {
    vector<segtree1d> tr;
    vector<ll> pl, pr;

    segtree() {
        tr.assign(1, segtree1d());
        pl.assign(1, -1);
        pr.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 2; i++) {
            tr.push_back(segtree1d());
            pl.push_back(-1);
            pr.push_back(-1);
        }
        pl[x] = tr.size() - 2;
        pr[x] = tr.size() - 1;
    }

    void update(ll x, ll l, ll r, ll X, ll Y, ll val) {
        // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << X << ' ' << Y << ' ' << val << '\n';
        if (l == r) {
            tr[x].update(0, 0, m, Y, val);
            return;
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        if (X <= mid) {
            update(pl[x], l, mid, X, Y, val);
        }
        else {
            update(pr[x], mid + 1, r, X, Y, val);
        }
        tr[x].update(0, 0, m, Y, gcd(tr[pl[x]].query(0, 0, m, Y, Y), tr[pr[x]].query(0, 0, m, Y, Y)));
    }

    ll query(ll x, ll l, ll r, ll LX, ll RX, ll LY, ll RY) {
        if (r < l) {
            return 0;
        }
        if (r < LX) {
            return 0;
        }
        if (RX < l) {
            return 0;
        }
        if (RX < LX) {
            return 0;
        }
        if (LX <= l && r <= RX) {
            return tr[x].query(0, 0, m, LY, RY);
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        return gcd(query(pl[x], l, mid, LX, RX, LY, RY), query(pr[x], mid + 1, r, LX, RX, LY, RY));
    }
};

segtree sg;

void init(int R, int C) {
    n = R;
    m = C;
    sg = segtree();
}

void update(int P, int Q, long long K) {
    sg.update(0, 0, n, P, Q, K);
    // cout << '\n';
    // cout << P << ' ' << Q << ' ' << K << endl;
}

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

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 583 ms 36084 KB Output is correct
5 Correct 421 ms 30256 KB Output is correct
6 Correct 672 ms 66500 KB Output is correct
7 Correct 655 ms 73048 KB Output is correct
8 Correct 599 ms 63520 KB Output is correct
9 Correct 711 ms 68448 KB Output is correct
10 Correct 648 ms 64236 KB Output is correct
11 Correct 0 ms 348 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 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 476 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 973 ms 39092 KB Output is correct
13 Correct 1035 ms 16724 KB Output is correct
14 Correct 702 ms 6740 KB Output is correct
15 Correct 1243 ms 24512 KB Output is correct
16 Correct 541 ms 54572 KB Output is correct
17 Correct 2173 ms 222652 KB Output is correct
18 Correct 2619 ms 229768 KB Output is correct
19 Correct 2688 ms 228724 KB Output is correct
20 Correct 2533 ms 227936 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 654 ms 35916 KB Output is correct
13 Correct 421 ms 30256 KB Output is correct
14 Correct 797 ms 66544 KB Output is correct
15 Correct 717 ms 72848 KB Output is correct
16 Correct 690 ms 63564 KB Output is correct
17 Correct 771 ms 68360 KB Output is correct
18 Correct 723 ms 64448 KB Output is correct
19 Correct 952 ms 39248 KB Output is correct
20 Correct 1104 ms 16920 KB Output is correct
21 Correct 763 ms 6816 KB Output is correct
22 Correct 1255 ms 24548 KB Output is correct
23 Correct 549 ms 54676 KB Output is correct
24 Correct 1910 ms 222844 KB Output is correct
25 Correct 2225 ms 229624 KB Output is correct
26 Correct 2127 ms 228800 KB Output is correct
27 Correct 2156 ms 227964 KB Output is correct
28 Runtime error 215 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 620 ms 36028 KB Output is correct
13 Correct 374 ms 30152 KB Output is correct
14 Correct 642 ms 66708 KB Output is correct
15 Correct 670 ms 73036 KB Output is correct
16 Correct 568 ms 63512 KB Output is correct
17 Correct 691 ms 69272 KB Output is correct
18 Correct 602 ms 64304 KB Output is correct
19 Correct 916 ms 39252 KB Output is correct
20 Correct 990 ms 16720 KB Output is correct
21 Correct 688 ms 6928 KB Output is correct
22 Correct 1200 ms 24568 KB Output is correct
23 Correct 496 ms 54464 KB Output is correct
24 Correct 1940 ms 222652 KB Output is correct
25 Correct 2162 ms 229828 KB Output is correct
26 Correct 2176 ms 228780 KB Output is correct
27 Correct 2145 ms 227884 KB Output is correct
28 Runtime error 225 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -