oj.uz

Submission #1081966

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

using namespace std;
using ll = int;

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

struct segtree1d {
    vector<long long> 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, long long 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]]);
    }

    long long 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, long long 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)));
    }

    long long 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 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 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 504 KB Output is correct
9 Correct 1 ms 600 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 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 539 ms 22644 KB Output is correct
5 Correct 373 ms 19856 KB Output is correct
6 Correct 578 ms 45876 KB Output is correct
7 Correct 629 ms 47428 KB Output is correct
8 Correct 465 ms 44240 KB Output is correct
9 Correct 552 ms 49724 KB Output is correct
10 Correct 550 ms 47468 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 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 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 388 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 834 ms 25048 KB Output is correct
13 Correct 1010 ms 9100 KB Output is correct
14 Correct 612 ms 1844 KB Output is correct
15 Correct 1260 ms 13952 KB Output is correct
16 Correct 469 ms 34748 KB Output is correct
17 Correct 1623 ms 146624 KB Output is correct
18 Correct 1918 ms 151228 KB Output is correct
19 Correct 1859 ms 150584 KB Output is correct
20 Correct 1868 ms 149772 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 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 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 555 ms 22456 KB Output is correct
13 Correct 389 ms 19932 KB Output is correct
14 Correct 593 ms 45908 KB Output is correct
15 Correct 555 ms 47356 KB Output is correct
16 Correct 492 ms 44260 KB Output is correct
17 Correct 608 ms 49716 KB Output is correct
18 Correct 538 ms 47368 KB Output is correct
19 Correct 838 ms 25116 KB Output is correct
20 Correct 1039 ms 9140 KB Output is correct
21 Correct 632 ms 1876 KB Output is correct
22 Correct 1254 ms 14024 KB Output is correct
23 Correct 545 ms 34752 KB Output is correct
24 Correct 1675 ms 146572 KB Output is correct
25 Correct 1799 ms 151228 KB Output is correct
26 Correct 1910 ms 150624 KB Output is correct
27 Correct 1788 ms 149692 KB Output is correct
28 Runtime error 285 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 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 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 0 ms 348 KB Output is correct
12 Correct 543 ms 22556 KB Output is correct
13 Correct 381 ms 19916 KB Output is correct
14 Correct 574 ms 45840 KB Output is correct
15 Correct 553 ms 47348 KB Output is correct
16 Correct 516 ms 44104 KB Output is correct
17 Correct 579 ms 49748 KB Output is correct
18 Correct 564 ms 47384 KB Output is correct
19 Correct 852 ms 25076 KB Output is correct
20 Correct 993 ms 9320 KB Output is correct
21 Correct 622 ms 1796 KB Output is correct
22 Correct 1245 ms 13952 KB Output is correct
23 Correct 471 ms 34744 KB Output is correct
24 Correct 1636 ms 146484 KB Output is correct
25 Correct 1868 ms 151228 KB Output is correct
26 Correct 1832 ms 150460 KB Output is correct
27 Correct 1870 ms 149636 KB Output is correct
28 Runtime error 304 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -