oj.uz

Submission #578908

# Submission time Handle Problem Language Result Execution time Memory
578908 2022-06-18T07:39:16 Z Mazaalai Game (IOI13_game) C++17
100 / 100
 4484 ms 114192 KB 
#include "game.h"
#include <bits/stdc++.h>
#define LINE "--------------------\n"
#define pb push_back
using namespace std;
using ll = long long;
int ST1, ST2, ED1, ED2;
ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct SegTree1D {
    int hasOne, child[2];
    ll val;
    SegTree1D() {
        hasOne = val = 0; // 0 means empty, -1 means not empty, hasOne > 0 means id
        child[0] = child[1] = -1;
    }
};
struct SegTree2D {
    int child[2], ptr;
    vector <SegTree1D> node;
    SegTree2D() {
        ptr = 1;
        node.pb(SegTree1D());
        child[0] = child[1] = -1;
    }
    void update2(int l, int r, int id, ll val, int head) {
        if (node[head].hasOne == id || node[head].hasOne == 0) {
            node[head].val = val;
            // cout << "UPDATED1: " << "(" << l << "," << r << ") " << id << " " << val << '\n';
            node[head].hasOne = id;
            return;
        }
        if (node[head].child[0] == -1) {
            node[head].child[0] = ptr++;
            node.pb(SegTree1D());
            node[head].child[1] = ptr++;
            node.pb(SegTree1D());
        }
 
        int mid = (l+r)>>1;
        if (node[head].hasOne > 0) {
            int tmp = node[head].hasOne; node[head].hasOne = -1;
            if (tmp <= mid) update2(l, mid, tmp, node[head].val, node[head].child[0]);
            else update2(mid+1, r, tmp, node[head].val, node[head].child[1]);
        }
        if (id <= mid) update2(l, mid, id, val, node[head].child[0]);
        else update2(mid+1, r, id, val, node[head].child[1]);
        node[head].val = gcd(
            node[ node[head].child[0] ].val,
            node[ node[head].child[1] ].val
        );
        // cout << "LR : " << node[ node[head].child[0] ].val << ',' << node[ node[head].child[1] ].val << '\n';
        // cout << "UPDATED2: " << "(" << l << "," << r << ") " << id << " " << node[head].val << '\n';
    }
    void update2(int id, ll val) {
        update2(ST2, ED2, id, val, 0);
    }
    ll query(int l, int r, int L, int R, int head) {
        if (head == -1 || l > R || L > r || node[head].hasOne == 0) return 0;
        if (node[head].hasOne > 0 && (node[head].hasOne > R || node[head].hasOne < L)) return 0;
        if (node[head].hasOne > 0) return node[head].val;
        if (L <= l && r <= R) return node[head].val;
        int mid = (l+r)>>1;
        return gcd(
            query(l, mid, L, R, node[head].child[0]),
            query(mid+1, r, L, R, node[head].child[1])
        );
    }
    ll query(int l, int r) {
        return query(ST2, ED2, l, r, 0);
    }
    ll query(int id) {
        return query(ST2, ED2, id, id, 0);
    }
};
vector <SegTree2D> node;
int ptr, X1, X2, Y1, Y2;
ll val;
void update1(int l, int r, int head) { // match X
    if (l == r) {
        node[head].update2(Y1, val);
        return;
    }
    if (node[head].child[0] == -1) {
        node[head].child[0] = ptr++;
        node.pb(SegTree2D());
        node[head].child[1] = ptr++;
        node.pb(SegTree2D());
    }
    int mid = (l+r)>>1;
    if (X1 <= mid) {
        update1(l, mid, node[head].child[0]);
    } else {
        update1(mid+1, r, node[head].child[1]);
    }
    ll tmp = gcd(
        node[ node[head].child[0] ].query(Y1), 
        node[ node[head].child[1] ].query(Y1)
    );
    node[head].update2(Y1, tmp);
    return;
}
ll query(int l, int r, int head) {
    if (l > X2 || X1 > r || head == -1) return 0;
    if (X1 <= l && r <= X2) return node[head].query(Y1, Y2);
    int mid = (l+r)>>1;
    return gcd(
        query(l, mid, node[head].child[0]),
        query(mid+1, r, node[head].child[1])
    );
}
void init(int R, int C) {
    ST1 = ST2 = 1;
    ED1 = R;
    ED2 = C;
    ptr = 1;
    node.pb(SegTree2D());
}
 
void update(int x, int y, ll K) {
    x++, y++;
    X1 = x;
    Y1 = y;
    val = K;
    // cout << LINE;
    // cout << "UPDATE: " << x << ' ' << y << ' ' << K << '\n';
    update1(ST1, ED1, 0);
    // for (int i = ST1; i <= ED1; i++)
    // for (int j = ST2; j <= ED2; j++) {
 
    //     X1 = X2 = i;
    //     Y1 = Y2 = j;
    //     cout << query(ST1, ED1, 0) << " \n"[j==3];
    // }
}
 
ll calculate(int x1, int y1, int x2, int y2) {
    x1++, y1++, x2++, y2++;
    X1 = x1;
    Y1 = y1;
    X2 = x2;
    Y2 = y2;
    // cout << "RES: ";
    return query(ST1, ED1, 0);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 436 ms 7740 KB Output is correct
5 Correct 303 ms 7948 KB Output is correct
6 Correct 380 ms 5244 KB Output is correct
7 Correct 394 ms 4956 KB Output is correct
8 Correct 282 ms 3856 KB Output is correct
9 Correct 387 ms 4692 KB Output is correct
10 Correct 358 ms 4256 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 700 ms 10812 KB Output is correct
13 Correct 1280 ms 4948 KB Output is correct
14 Correct 281 ms 928 KB Output is correct
15 Correct 1486 ms 6660 KB Output is correct
16 Correct 194 ms 8956 KB Output is correct
17 Correct 563 ms 5856 KB Output is correct
18 Correct 898 ms 9504 KB Output is correct
19 Correct 820 ms 9400 KB Output is correct
20 Correct 724 ms 8856 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 429 ms 7728 KB Output is correct
13 Correct 309 ms 8128 KB Output is correct
14 Correct 373 ms 5172 KB Output is correct
15 Correct 403 ms 4896 KB Output is correct
16 Correct 279 ms 3736 KB Output is correct
17 Correct 388 ms 4608 KB Output is correct
18 Correct 387 ms 4224 KB Output is correct
19 Correct 695 ms 10808 KB Output is correct
20 Correct 1265 ms 4996 KB Output is correct
21 Correct 268 ms 1024 KB Output is correct
22 Correct 1478 ms 6620 KB Output is correct
23 Correct 186 ms 8876 KB Output is correct
24 Correct 564 ms 5864 KB Output is correct
25 Correct 893 ms 9424 KB Output is correct
26 Correct 838 ms 9352 KB Output is correct
27 Correct 763 ms 8912 KB Output is correct
28 Correct 545 ms 57020 KB Output is correct
29 Correct 1108 ms 49504 KB Output is correct
30 Correct 3544 ms 43980 KB Output is correct
31 Correct 3352 ms 35796 KB Output is correct
32 Correct 574 ms 10924 KB Output is correct
33 Correct 712 ms 14344 KB Output is correct
34 Correct 282 ms 43112 KB Output is correct
35 Correct 817 ms 29068 KB Output is correct
36 Correct 1393 ms 47332 KB Output is correct
37 Correct 1187 ms 47600 KB Output is correct
38 Correct 1175 ms 47040 KB Output is correct
39 Correct 992 ms 39652 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 450 ms 7632 KB Output is correct
13 Correct 318 ms 7936 KB Output is correct
14 Correct 381 ms 5388 KB Output is correct
15 Correct 398 ms 4984 KB Output is correct
16 Correct 285 ms 3592 KB Output is correct
17 Correct 386 ms 4672 KB Output is correct
18 Correct 353 ms 4248 KB Output is correct
19 Correct 719 ms 10736 KB Output is correct
20 Correct 1298 ms 4944 KB Output is correct
21 Correct 282 ms 1028 KB Output is correct
22 Correct 1487 ms 6524 KB Output is correct
23 Correct 195 ms 8856 KB Output is correct
24 Correct 594 ms 5708 KB Output is correct
25 Correct 922 ms 9328 KB Output is correct
26 Correct 801 ms 9524 KB Output is correct
27 Correct 727 ms 8780 KB Output is correct
28 Correct 523 ms 57040 KB Output is correct
29 Correct 1065 ms 49528 KB Output is correct
30 Correct 3545 ms 43948 KB Output is correct
31 Correct 3379 ms 35860 KB Output is correct
32 Correct 588 ms 11076 KB Output is correct
33 Correct 754 ms 14360 KB Output is correct
34 Correct 278 ms 43124 KB Output is correct
35 Correct 774 ms 29368 KB Output is correct
36 Correct 1432 ms 47368 KB Output is correct
37 Correct 1148 ms 47624 KB Output is correct
38 Correct 1135 ms 46892 KB Output is correct
39 Correct 807 ms 114192 KB Output is correct
40 Correct 1608 ms 89732 KB Output is correct
41 Correct 4484 ms 85180 KB Output is correct
42 Correct 4323 ms 67596 KB Output is correct
43 Correct 525 ms 84788 KB Output is correct
44 Correct 847 ms 11132 KB Output is correct
45 Correct 994 ms 39424 KB Output is correct
46 Correct 1882 ms 88556 KB Output is correct
47 Correct 1842 ms 88444 KB Output is correct
48 Correct 1794 ms 88112 KB Output is correct
49 Correct 1 ms 212 KB Output is correct