oj.uz

Submission #1009468

# Submission time Handle Problem Language Result Execution time Memory
1009468 2024-06-27T14:45:22 Z c2zi6 Game (IOI13_game) C++14
63 / 100
 3764 ms 137692 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "game.h"

struct SEGTREE {
    int n;
    VL tree;
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VL(2*n);
    }
    ll get(int N, int L, int R, int l, int r) {
        if (l <= L && R <= r) return tree[N];
        if (R < l || L > r) return 0;
        int M = (L + R) / 2;
        return __gcd(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
    }
    void upd(int N, int L, int R, int i, ll s) {
        if (R < i || L > i) return;
        if (L == R) {
            tree[N] = s;
            return;
        }
        int M = (L + R) / 2;
        upd(2*N+1, L, M, i, s);
        upd(2*N+2, M+1, R, i, s);
        tree[N] = __gcd(tree[2*N+1], tree[2*N+2]);
    }
    ll get(int l, int r) {
        return get(0, 0, n-1, l, r);
    }
    void upd(int i, ll s) {
        upd(0, 0, n-1, i, s);
    }
};

SEGTREE gcd(SEGTREE a, SEGTREE b) {
    int n = a.tree.size();
    rep(i, n) a.tree[i] = __gcd(a.tree[i], b.tree[i]);
    return a;
}

struct SEGTREESQ {
    int n;
    vector<SEGTREE> tree;
    SEGTREESQ(){}
    SEGTREESQ(int sz, int m) {
        n = 1;
        while (n < sz) n *= 2;
        tree = vector<SEGTREE>(2*n, SEGTREE(m));
    }
    ll get(int N, int L, int R, int l, int r, int jl, int jr) {
        if (l <= L && R <= r) return tree[N].get(jl, jr);
        if (R < l || L > r) return 0;
        int M = (L + R) / 2;
        return __gcd(get(2*N+1, L, M, l, r, jl, jr), get(2*N+2, M+1, R, l, r, jl, jr));
    }
    void upd(int N, int L, int R, int i, int j, ll s) {
        if (R < i || L > i) return;
        if (L == R) {
            tree[N].upd(j, s);
            return;
        }
        int M = (L + R) / 2;
        upd(2*N+1, L, M, i, j, s);
        upd(2*N+2, M+1, R, i, j, s);
        tree[N] = gcd(tree[2*N+1], tree[2*N+2]);
    }
    ll get(int il, int ir, int jl, int jr) {
        return get(0, 0, n-1, il, ir, jl, jr);
    }
    void upd(int i, int j, ll s) {
        upd(0, 0, n-1, i, j, s);
    }
};

SEGTREESQ ds;
vector<SEGTREE> ds2;
bool isds2;
 
void init(int n, int m) {
    if (n <= 10) {
        isds2 = true;
        ds2 = vector<SEGTREE>(n, SEGTREE(m));
    } else {
        isds2 = false;
        ds = SEGTREESQ(n, m);
    }
}

void update(int x, int y, ll s) {
    if (isds2) ds2[x].upd(y, s);
    else ds.upd(x, y, s);
}

ll calculate(int il, int jl, int ir, int jr) {
    if (isds2) {
        ll ret = 0;
        replr(i, il, ir) {
            ret = __gcd(ret, ds2[i].get(jl, jr));
        }
        return ret;
    }
    return ds.get(il, ir, jl, jr);
}

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 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 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 860 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 348 KB Output is correct
4 Correct 545 ms 25240 KB Output is correct
5 Correct 350 ms 26248 KB Output is correct
6 Correct 422 ms 23112 KB Output is correct
7 Correct 436 ms 23044 KB Output is correct
8 Correct 327 ms 23880 KB Output is correct
9 Correct 410 ms 23068 KB Output is correct
10 Correct 352 ms 22876 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 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1024 ms 37304 KB Output is correct
13 Correct 1197 ms 33876 KB Output is correct
14 Correct 989 ms 132432 KB Output is correct
15 Correct 1670 ms 132552 KB Output is correct
16 Correct 2792 ms 132640 KB Output is correct
17 Correct 1670 ms 133504 KB Output is correct
18 Correct 3402 ms 132912 KB Output is correct
19 Correct 3507 ms 133100 KB Output is correct
20 Correct 3764 ms 132640 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 586 ms 25256 KB Output is correct
13 Correct 409 ms 26280 KB Output is correct
14 Correct 438 ms 23248 KB Output is correct
15 Correct 440 ms 22976 KB Output is correct
16 Correct 368 ms 23892 KB Output is correct
17 Correct 426 ms 23116 KB Output is correct
18 Correct 386 ms 22904 KB Output is correct
19 Correct 1035 ms 39140 KB Output is correct
20 Correct 1063 ms 37204 KB Output is correct
21 Correct 956 ms 136436 KB Output is correct
22 Correct 1703 ms 136528 KB Output is correct
23 Correct 2646 ms 136340 KB Output is correct
24 Correct 1558 ms 136980 KB Output is correct
25 Correct 3237 ms 137228 KB Output is correct
26 Correct 3349 ms 137404 KB Output is correct
27 Correct 3582 ms 136788 KB Output is correct
28 Runtime error 2 ms 600 KB Execution killed with signal 6
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 0 ms 860 KB Output is correct
6 Correct 1 ms 792 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 960 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 521 ms 25448 KB Output is correct
13 Correct 337 ms 26184 KB Output is correct
14 Correct 399 ms 23112 KB Output is correct
15 Correct 447 ms 22944 KB Output is correct
16 Correct 314 ms 23880 KB Output is correct
17 Correct 411 ms 22940 KB Output is correct
18 Correct 406 ms 22872 KB Output is correct
19 Correct 1022 ms 39220 KB Output is correct
20 Correct 1122 ms 37200 KB Output is correct
21 Correct 964 ms 136180 KB Output is correct
22 Correct 1619 ms 136528 KB Output is correct
23 Correct 2566 ms 136168 KB Output is correct
24 Correct 1653 ms 137164 KB Output is correct
25 Correct 3207 ms 137372 KB Output is correct
26 Correct 3241 ms 137692 KB Output is correct
27 Correct 3402 ms 136748 KB Output is correct
28 Runtime error 2 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -