oj.uz

Submission #1077897

# Submission time Handle Problem Language Result Execution time Memory
1077897 2024-08-27T10:15:37 Z TheQuantiX Game (IOI13_game) C++17
37 / 100
 13000 ms 19492 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 (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];
        }
        if (ur[x] == -1) {
            extend(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 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 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 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 344 KB Output is correct
12 Correct 0 ms 440 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 1004 ms 19484 KB Output is correct
5 Correct 693 ms 19312 KB Output is correct
6 Correct 639 ms 18556 KB Output is correct
7 Correct 771 ms 16748 KB Output is correct
8 Correct 475 ms 12152 KB Output is correct
9 Correct 733 ms 16748 KB Output is correct
10 Correct 714 ms 16336 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 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4621 ms 13784 KB Output is correct
13 Execution timed out 13063 ms 6080 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 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 1 ms 432 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1114 ms 19304 KB Output is correct
13 Correct 667 ms 19380 KB Output is correct
14 Correct 693 ms 18560 KB Output is correct
15 Correct 845 ms 16696 KB Output is correct
16 Correct 470 ms 12124 KB Output is correct
17 Correct 789 ms 16876 KB Output is correct
18 Correct 765 ms 16236 KB Output is correct
19 Correct 5017 ms 13804 KB Output is correct
20 Execution timed out 13048 ms 6256 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 600 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 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 1 ms 348 KB Output is correct
12 Correct 1014 ms 19492 KB Output is correct
13 Correct 675 ms 19312 KB Output is correct
14 Correct 645 ms 18556 KB Output is correct
15 Correct 768 ms 16744 KB Output is correct
16 Correct 456 ms 12168 KB Output is correct
17 Correct 702 ms 16744 KB Output is correct
18 Correct 733 ms 16236 KB Output is correct
19 Correct 4622 ms 13832 KB Output is correct
20 Execution timed out 13073 ms 6196 KB Time limit exceeded
21 Halted 0 ms 0 KB -