oj.uz

Submission #957460

# Submission time Handle Problem Language Result Execution time Memory
957460 2024-04-03T18:41:41 Z bobbilyking Game (IOI13_game) C++17
63 / 100
 1159 ms 256000 KB 
#include "game.h"

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }


int MAXR, MAXC;

struct Seg1D {
    Seg1D* c[2]{};
    ll val = 0;

    void modify(int l, int r, int i, long long k) {
        if (l == r) {
            val = k; return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            if (!c[0]) c[0] = new Seg1D();
            c[0]->modify(l, m, i, k);
        } else {
            if (!c[1]) c[1] = new Seg1D();
            c[1]->modify(m+1, r, i, k); 
        }
        val = 0;
        F(i, 0, 2) if (c[i]) val = gcd(val, c[i]->val);
    }

    ll query(int l, int r, int qxl, int qxr) {
        ll res = 0;
        if (qxr < l || r < qxl) return 0;
        if (qxl <= l and r <= qxr) {
            return val;
        }
        int m = (l + r) / 2;
        if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr));
        if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr));
        return res;
    }
};

struct Seg2D { // outer layer of segtrees
    Seg2D* c[2]{};
    Seg1D* repr = new Seg1D();

    void modify(int l, int r, int x, int y, long long k) {
        // log(n) segtree representations 
        if (l == r) { // leaf node direct modify
            repr->modify(0, MAXC, y, k);
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            if (!c[0]) c[0] = new Seg2D();
            c[0]->modify(l, m, x, y, k);
        } else {
            if (!c[1]) c[1] = new Seg2D();
            c[1]->modify(m+1, r, x, y, k); 
        }

        // real simple but nice idea: universes aren't disjoint! We can merge info here.
        // Now we can handle multiple keys ezpz
        ll val = 0;
        if (c[0]) val = gcd(val, c[0]->repr->query(0, MAXC, y, y));
        if (c[1]) val = gcd(val, c[1]->repr->query(0, MAXC, y, y));
        repr->modify(0, MAXC, y, val);
    }

    ll query(int l, int r, int qxl, int qxr, pair<int, int> yrange) {
        if (qxr < l || r < qxl) return 0;
        // cout << "HAHA " << l << " " << r << " | " << qxl << " " << qxr << endl;
        if (qxl <= l and r <= qxr) {
            // cout << "HOW THE FUCK " << endl;
            // cout << "ADDRESS OF THIS NODE: " << this << endl;
            // cout << l << " " << r << " INCLUDED " << endl;
            // cout << "PULL FROM REPR " << endl;
            return repr->query(0, MAXC, yrange.K, yrange.V);
        }
        ll res = 0;

        int m = (l + r) / 2;

        // cout << "AT " << l << " " << r << " SHOULD DEF HAVE " << c[0] << endl;
        if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr, yrange));
        if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr, yrange));

        // cout << "WAT " << res << endl;
        return res;
    }
} root;

void init(int R, int C) {
    MAXR = R-1, MAXC = C-1;
}

void update(int P, int Q, long long k) {
    root.modify(0, MAXR, P, Q, k);
}

long long calculate(int p, int q, int u, int v) {
    /* ... */
    assert(p <= u and u <= MAXR);
    assert(q <= v and v <= MAXC);
    return root.query(0, MAXR, p, u, make_pair(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 432 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 344 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 344 KB Output is correct
10 Correct 0 ms 348 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 375 ms 15480 KB Output is correct
5 Correct 263 ms 15184 KB Output is correct
6 Correct 318 ms 12368 KB Output is correct
7 Correct 358 ms 12116 KB Output is correct
8 Correct 250 ms 8928 KB Output is correct
9 Correct 355 ms 12196 KB Output is correct
10 Correct 321 ms 11844 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 756 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 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 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 567 ms 18108 KB Output is correct
13 Correct 894 ms 8572 KB Output is correct
14 Correct 186 ms 3612 KB Output is correct
15 Correct 1018 ms 11192 KB Output is correct
16 Correct 164 ms 20520 KB Output is correct
17 Correct 540 ms 14164 KB Output is correct
18 Correct 853 ms 21492 KB Output is correct
19 Correct 768 ms 21564 KB Output is correct
20 Correct 701 ms 20992 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 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 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 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 365 ms 15164 KB Output is correct
13 Correct 261 ms 15400 KB Output is correct
14 Correct 316 ms 12368 KB Output is correct
15 Correct 360 ms 12064 KB Output is correct
16 Correct 244 ms 9044 KB Output is correct
17 Correct 358 ms 12444 KB Output is correct
18 Correct 316 ms 11836 KB Output is correct
19 Correct 568 ms 18212 KB Output is correct
20 Correct 901 ms 8364 KB Output is correct
21 Correct 186 ms 3568 KB Output is correct
22 Correct 1033 ms 11376 KB Output is correct
23 Correct 161 ms 20636 KB Output is correct
24 Correct 548 ms 14320 KB Output is correct
25 Correct 830 ms 21628 KB Output is correct
26 Correct 730 ms 21592 KB Output is correct
27 Correct 685 ms 20820 KB Output is correct
28 Correct 653 ms 256000 KB Output is correct
29 Runtime error 1128 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 424 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 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 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 380 ms 15436 KB Output is correct
13 Correct 267 ms 15196 KB Output is correct
14 Correct 323 ms 12648 KB Output is correct
15 Correct 341 ms 12096 KB Output is correct
16 Correct 260 ms 9244 KB Output is correct
17 Correct 333 ms 12372 KB Output is correct
18 Correct 318 ms 12204 KB Output is correct
19 Correct 590 ms 18520 KB Output is correct
20 Correct 901 ms 8384 KB Output is correct
21 Correct 188 ms 3412 KB Output is correct
22 Correct 1016 ms 11488 KB Output is correct
23 Correct 158 ms 20652 KB Output is correct
24 Correct 543 ms 14060 KB Output is correct
25 Correct 857 ms 21464 KB Output is correct
26 Correct 758 ms 21840 KB Output is correct
27 Correct 691 ms 20980 KB Output is correct
28 Correct 665 ms 256000 KB Output is correct
29 Runtime error 1159 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -