oj.uz

Submission #423041

# Submission time Handle Problem Language Result Execution time Memory
423041 2021-06-10T16:22:06 Z wiwiho Game (IOI13_game) C++14
100 / 100
 5453 ms 95228 KB 
#include "game.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct Node1D{
    ll v = 0;
    int tag = -1;
    Node1D *l = nullptr, *r = nullptr;
};

struct Node2D{
    Node1D *rt = nullptr;
    Node2D *l = nullptr, *r = nullptr;
};

int n, m;
Node2D *rt = nullptr;

void pull1D(Node1D *node){
    node->v = __gcd(node->l == nullptr ? 0 : node->l->v, node->r == nullptr ? 0 : node->r->v);
}

Node1D *modify1D(int pos, ll v, int L, int R, Node1D *node){
    if(node == nullptr){
        node = new Node1D();
        node->v = v;
        node->tag = pos;
        return node;
    }
    if(pos == node->tag){
        node->v = v;
        return node;
    }
    assert(L != R);
    int M = (L + R) / 2;
    if(node->tag != -1){
        assert(node->l == nullptr && node->r == nullptr);
        if(node->tag <= M) node->l = modify1D(node->tag, node->v, L, M, node->l);
        else node->r = modify1D(node->tag, node->v, M + 1, R, node->r);
        node->tag = -1;
        node->v = 0;
    }
    if(pos <= M) node->l = modify1D(pos, v, L, M, node->l);
    else node->r = modify1D(pos, v, M + 1, R, node->r);
    pull1D(node);
    return node;
}

ll query1D(int l, int r, int L, int R, Node1D *node){
    if(node == nullptr) return 0;
    if((l <= node->tag && node->tag <= r) || (l == L && r == R)) return node->v;
    assert(L != R);
    int M = (L + R) / 2;
    if(r <= M) return query1D(l, r, L, M, node->l);
    else if(l > M) return query1D(l, r, M + 1, R, node->r);
    else return __gcd(query1D(l, M, L, M, node->l), query1D(M + 1, r, M + 1, R, node->r));
}

void pull2D(Node2D *node, int y){
    ll lv = node->l == nullptr ? 0 : query1D(y, y, 0, m - 1, node->l->rt);
    ll rv = node->r == nullptr ? 0 : query1D(y, y, 0, m - 1, node->r->rt);
    node->rt = modify1D(y, __gcd(lv, rv), 0, m - 1, node->rt);
}

Node2D *modify2D(int x, int y, ll v, int L, int R, Node2D *node){
    if(node == nullptr) node = new Node2D();
    if(L == R){
        node->rt = modify1D(y, v, 0, m - 1, node->rt);
        return node;
    }
    int M = (L + R) / 2;
    if(x <= M) node->l = modify2D(x, y, v, L, M, node->l);
    else node->r = modify2D(x, y, v, M + 1, R, node->r);
    pull2D(node, y);
    return node;
}

ll query2D(int xl, int xr, int yl, int yr, int L, int R, Node2D *node){
    if(node == nullptr) return 0;
    if(xl == L && xr == R){
        return query1D(yl, yr, 0, m - 1, node->rt);
    }
    int M = (L + R) / 2;
    if(xr <= M) return query2D(xl, xr, yl, yr, L, M, node->l);
    else if(xl > M) return query2D(xl, xr, yl, yr, M + 1, R, node->r);
    else return __gcd(query2D(xl, M, yl, yr, L, M, node->l), query2D(M + 1, xr, yl, yr, M + 1, R, node->r));
}

void init(int R, int C){
    n = R; m = C;
}

void update(int P, int Q, long long K){
    rt = modify2D(P, Q, K, 0, n - 1, rt);
}

ll calculate(int P, int Q, int U, int V){
    return query2D(P, U, Q, V, 0, n - 1, rt);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 501 ms 10616 KB Output is correct
5 Correct 417 ms 13288 KB Output is correct
6 Correct 418 ms 10792 KB Output is correct
7 Correct 451 ms 10516 KB Output is correct
8 Correct 300 ms 8468 KB Output is correct
9 Correct 479 ms 10556 KB Output is correct
10 Correct 392 ms 10212 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 900 ms 13332 KB Output is correct
13 Correct 1503 ms 9688 KB Output is correct
14 Correct 278 ms 5836 KB Output is correct
15 Correct 1781 ms 11944 KB Output is correct
16 Correct 215 ms 15392 KB Output is correct
17 Correct 655 ms 11676 KB Output is correct
18 Correct 1227 ms 16832 KB Output is correct
19 Correct 1020 ms 17008 KB Output is correct
20 Correct 897 ms 16440 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 497 ms 10564 KB Output is correct
13 Correct 411 ms 13380 KB Output is correct
14 Correct 432 ms 10712 KB Output is correct
15 Correct 476 ms 10524 KB Output is correct
16 Correct 320 ms 8372 KB Output is correct
17 Correct 422 ms 10540 KB Output is correct
18 Correct 395 ms 10260 KB Output is correct
19 Correct 867 ms 16536 KB Output is correct
20 Correct 1521 ms 9828 KB Output is correct
21 Correct 288 ms 5572 KB Output is correct
22 Correct 1787 ms 11776 KB Output is correct
23 Correct 215 ms 15428 KB Output is correct
24 Correct 620 ms 11760 KB Output is correct
25 Correct 1263 ms 16928 KB Output is correct
26 Correct 962 ms 16884 KB Output is correct
27 Correct 889 ms 16420 KB Output is correct
28 Correct 518 ms 48196 KB Output is correct
29 Correct 1334 ms 43340 KB Output is correct
30 Correct 4130 ms 43444 KB Output is correct
31 Correct 3960 ms 34580 KB Output is correct
32 Correct 559 ms 10496 KB Output is correct
33 Correct 613 ms 14008 KB Output is correct
34 Correct 357 ms 37104 KB Output is correct
35 Correct 1086 ms 25556 KB Output is correct
36 Correct 1972 ms 41104 KB Output is correct
37 Correct 1431 ms 41348 KB Output is correct
38 Correct 1449 ms 40864 KB Output is correct
39 Correct 1107 ms 34140 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 549 ms 10464 KB Output is correct
13 Correct 409 ms 13216 KB Output is correct
14 Correct 405 ms 10840 KB Output is correct
15 Correct 489 ms 10528 KB Output is correct
16 Correct 336 ms 8476 KB Output is correct
17 Correct 445 ms 10564 KB Output is correct
18 Correct 405 ms 10252 KB Output is correct
19 Correct 863 ms 16484 KB Output is correct
20 Correct 1501 ms 9716 KB Output is correct
21 Correct 278 ms 5636 KB Output is correct
22 Correct 1814 ms 11848 KB Output is correct
23 Correct 213 ms 15436 KB Output is correct
24 Correct 619 ms 11664 KB Output is correct
25 Correct 1270 ms 16912 KB Output is correct
26 Correct 982 ms 16972 KB Output is correct
27 Correct 998 ms 16396 KB Output is correct
28 Correct 616 ms 48424 KB Output is correct
29 Correct 1390 ms 43316 KB Output is correct
30 Correct 4317 ms 43392 KB Output is correct
31 Correct 4035 ms 34564 KB Output is correct
32 Correct 464 ms 10544 KB Output is correct
33 Correct 595 ms 14056 KB Output is correct
34 Correct 298 ms 37244 KB Output is correct
35 Correct 918 ms 25616 KB Output is correct
36 Correct 1972 ms 41200 KB Output is correct
37 Correct 1513 ms 41540 KB Output is correct
38 Correct 1436 ms 40872 KB Output is correct
39 Correct 793 ms 95228 KB Output is correct
40 Correct 2128 ms 78828 KB Output is correct
41 Correct 5453 ms 85832 KB Output is correct
42 Correct 5032 ms 66296 KB Output is correct
43 Correct 479 ms 73668 KB Output is correct
44 Correct 609 ms 10964 KB Output is correct
45 Correct 1116 ms 34004 KB Output is correct
46 Correct 2404 ms 77672 KB Output is correct
47 Correct 2515 ms 77792 KB Output is correct
48 Correct 2478 ms 77368 KB Output is correct
49 Correct 1 ms 204 KB Output is correct