oj.uz

Submission #1077902

# Submission time Handle Problem Language Result Execution time Memory
1077902 2024-08-27T10:19:20 Z TheQuantiX Game (IOI13_game) C++17
37 / 100
 13000 ms 15400 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 segtree {
    vector<ll> tr;
    vector<ll> ur, ul, dr, dl;

    segtree() {
        tr.assign(1, 0);
        ur.assign(1, -1);
        ul.assign(1, -1);
        dr.assign(1, -1);
        dl.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 4; i++) {
            tr.push_back(0);
            ul.push_back(-1);
            ur.push_back(-1);
            dl.push_back(-1);
            dr.push_back(-1);
        }
        ul[x] = tr.size() - 4;
        ur[x] = tr.size() - 3;
        dl[x] = tr.size() - 2;
        dr[x] = tr.size() - 1;
    }

    void update(ll x, ll lx, ll rx, ll ly, ll ry, ll X, ll Y, ll val) {
        if (lx == rx && ly == ry) {
            tr[x] = val;
            return;
        }
        if (ur[x] == -1) {
            extend(x);
        }
        ll midx = (rx + lx) / 2;
        ll midy = (ry + ly) / 2;
        if (X <= midx) {
            if (Y <= midy) {
                update(ul[x], lx, midx, ly, midy, X, Y, val);
            }
            else {
                update(ur[x], lx, midx, midy + 1, ry, X, Y, val);
            }
        }
        else {
            if (Y <= midy) {
                update(dl[x], midx + 1, rx, ly, midy, X, Y, val);
            }
            else {
                update(dr[x], midx + 1, rx, midy + 1, ry, X, Y, val);
            }
        }
        tr[x] = gcd(gcd(tr[ul[x]], tr[ur[x]]), gcd(tr[dl[x]], tr[dr[x]]));
    }

    ll query(ll x, ll lx, ll rx, ll ly, ll ry, ll LX, ll RX, ll LY, ll RY) {
        if (x == -1) {
            return 0;
        }
        if (tr[x] == 0) {
            return 0;
        }
        if (rx < lx) {
            return 0;
        }
        if (rx < LX) {
            return 0;
        }
        if (RX < lx) {
            return 0;
        }
        if (RX < LX) {
            return 0;
        }
        if (ry < ly) {
            return 0;
        }
        if (ry < LY) {
            return 0;
        }
        if (RY < ly) {
            return 0;
        }
        if (RY < LY) {
            return 0;
        }
        if (LX <= lx && rx <= RX && LY <= ly && ry <= RY) {
            return tr[x];
        }
        ll midx = (rx + lx) / 2;
        ll midy = (ry + ly) / 2;
        return gcd(
                    gcd(query(ul[x], lx, midx,     ly, midy, LX, RX, LY, RY), query(ur[x], lx, midx,     midy + 1, ry, LX, RX, LY, RY)), 
                    gcd(query(dl[x], midx + 1, rx, ly, midy, LX, RX, LY, RY), query(dr[x], midx + 1, rx, midy + 1, ry, 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, 0, m, P, Q, K);
    // cout << P << ' ' << Q << ' ' << K << endl;
}

long long calculate(int P, int Q, int U, int V) {
    return sg.query(0, 0, n, 0, m, 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 348 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 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 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 0 ms 344 KB Output is correct
4 Correct 1040 ms 14948 KB Output is correct
5 Correct 662 ms 15400 KB Output is correct
6 Correct 645 ms 13916 KB Output is correct
7 Correct 769 ms 12924 KB Output is correct
8 Correct 459 ms 8172 KB Output is correct
9 Correct 729 ms 13172 KB Output is correct
10 Correct 713 ms 12856 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 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 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 4791 ms 9736 KB Output is correct
13 Execution timed out 13045 ms 3080 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 991 ms 15036 KB Output is correct
13 Correct 674 ms 15244 KB Output is correct
14 Correct 626 ms 13792 KB Output is correct
15 Correct 764 ms 12940 KB Output is correct
16 Correct 443 ms 8084 KB Output is correct
17 Correct 723 ms 13180 KB Output is correct
18 Correct 685 ms 12928 KB Output is correct
19 Correct 4760 ms 9728 KB Output is correct
20 Execution timed out 13046 ms 3164 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 420 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 995 ms 15080 KB Output is correct
13 Correct 672 ms 15228 KB Output is correct
14 Correct 627 ms 14124 KB Output is correct
15 Correct 790 ms 12936 KB Output is correct
16 Correct 453 ms 8084 KB Output is correct
17 Correct 721 ms 13280 KB Output is correct
18 Correct 716 ms 12924 KB Output is correct
19 Correct 4681 ms 9576 KB Output is correct
20 Execution timed out 13054 ms 2992 KB Time limit exceeded
21 Halted 0 ms 0 KB -