oj.uz

Submission #1094116

# Submission time Handle Problem Language Result Execution time Memory
1094116 2024-09-28T12:53:23 Z ASIXER Game (IOI13_game) C++17
80 / 100
 2009 ms 135328 KB 
#include "game.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;

struct YNode {
    int lb, rb;
    int x_root = -1;
    int lc = -1, rc = -1;
} y_tree[5000000];
struct XNode {
    int lb, rb;
    ll val = 0;
    int lc = -1, rc = -1;
} x_tree[1000000];

int r, c, q;
int y_cnt = 0, x_cnt = 0;

int init_x_node(int lb, int rb) {
    XNode& x_node = x_tree[x_cnt];
    x_node.lb = lb, x_node.rb = rb;
    return x_cnt++;
}
int init_y_node(int lb, int rb) {
    YNode& y_node = y_tree[y_cnt];
    y_node.lb = lb, y_node.rb = rb;
    y_node.x_root = init_x_node(1, c);
    return y_cnt++;
}

ll x_query(XNode& x_node, int xl, int xr) {
    // cout << "x query " << x_node.lb << " ~ " << x_node.rb << " (qrange: " << xl << " ~ " << xr << ")\n";
    if (xr < x_node.lb || x_node.rb < xl) return 0;
    else if (xl <= x_node.lb && x_node.rb <= xr) return x_node.val;
    ll ret = 0;
    if (x_node.lc != -1) ret = gcd(ret, x_query(x_tree[x_node.lc], xl, xr));
    if (x_node.rc != -1) ret = gcd(ret, x_query(x_tree[x_node.rc], xl, xr));
    return ret;
}
ll y_query(YNode& y_node, int yl, int yr, int xl, int xr) {
    // cout << "y query " << y_node.lb << " ~ " << y_node.rb << " (qr: " << yl << " ~ " << yr << ")\n";
    if (yr < y_node.lb || y_node.rb < yl) return 0;
    else if (yl <= y_node.lb && y_node.rb <= yr) return x_query(x_tree[y_node.x_root], xl, xr);
    ll ret = 0;
    if (y_node.lc != -1) ret = gcd(ret, y_query(y_tree[y_node.lc], yl, yr, xl, xr));
    if (y_node.rc != -1) ret = gcd(ret, y_query(y_tree[y_node.rc], yl, yr, xl, xr));
    return ret;
}

void x_update(XNode& x_node, int x, ll val) {
    if (x < x_node.lb || x_node.rb < x) return;
    if (x_node.lb == x_node.rb) {
        x_node.val = val;
        return;
    }
    int mid = (x_node.lb + x_node.rb) >> 1;
    if (x <= mid) {
        if (x_node.lc == -1) {
            x_node.lc = init_x_node(x, x);
            XNode& lcn = x_tree[x_node.lc];
            x_update(lcn, x, val);
        } else {
            XNode& lcn = x_tree[x_node.lc];
            if (lcn.lb <= x && x <= lcn.rb) x_update(lcn, x, val);
            else {
                int mmid = (x_node.lb + mid) >> 1;
                int new_lc_idx = init_x_node(x_node.lb, mid);
                XNode& new_lcn = x_tree[new_lc_idx];
                if (lcn.rb <= mmid) new_lcn.lc = x_node.lc;
                else new_lcn.rc = x_node.lc;
                x_node.lc = new_lc_idx;
                x_update(new_lcn, x, val);
            }
        }
    } else {
        if (x_node.rc == -1) {
            x_node.rc = init_x_node(x, x);
            XNode& rcn = x_tree[x_node.rc];
            x_update(rcn, x, val);
        } else {
            XNode& rcn = x_tree[x_node.rc];
            if (rcn.lb <= x && x <= rcn.rb) x_update(rcn, x, val);
            else {
                int mmid = (mid + 1 + x_node.rb) >> 1;
                int new_rc_idx = init_x_node(mid + 1, x_node.rb);
                XNode& new_rcn = x_tree[new_rc_idx];
                if (rcn.rb <= mmid) new_rcn.lc = x_node.rc;
                else new_rcn.rc = x_node.rc;
                x_node.rc = new_rc_idx;
                x_update(new_rcn, x, val);
            }
        }
    }

    ll new_val = 0;
    if (x_node.lc != -1) new_val = gcd(new_val, x_tree[x_node.lc].val);
    if (x_node.rc != -1) new_val = gcd(new_val, x_tree[x_node.rc].val);
    // cout << "x upd result: " << x_node.lb << " " << x_node.rb << ": " << new_val << "\n";
    x_node.val = new_val;
}

void y_update(YNode& y_node, int y, int x, ll val) {
    // cout << "y upd " << y_node.lb << " ~ " << y_node.rb << " (p: " << y << ")\n";
    if (y < y_node.lb || y_node.rb < y) return;
    if (y_node.lb == y_node.rb) return x_update(x_tree[y_node.x_root], x, val);
    int mid = (y_node.lb + y_node.rb) >> 1;
    if (y <= mid) {
        if (y_node.lc == -1) y_node.lc = init_y_node(y_node.lb, mid);
        y_update(y_tree[y_node.lc], y, x, val);
    } else {
        if (y_node.rc == -1) y_node.rc = init_y_node(mid + 1, y_node.rb);
        y_update(y_tree[y_node.rc], y, x, val);
    }

    ll new_val = 0;
    if (y_node.lc != -1) new_val = gcd(new_val, x_query(x_tree[y_tree[y_node.lc].x_root], x, x));
    if (y_node.rc != -1) new_val = gcd(new_val, x_query(x_tree[y_tree[y_node.rc].x_root], x, x));
    x_update(x_tree[y_node.x_root], x, new_val);
}

void init(int rr, int cc) { r = rr, c = cc, init_y_node(1, r); }

void update(int y, int x, ll k) { y_update(y_tree[0], y + 1, x + 1, k); }

ll calculate(int y1, int x1, int y2, int x2) { return y_query(y_tree[0], y1 + 1, y2 + 1, x1 + 1, x2 + 1); }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 121684 KB Output is correct
2 Correct 47 ms 121692 KB Output is correct
3 Correct 48 ms 121504 KB Output is correct
4 Correct 48 ms 121680 KB Output is correct
5 Correct 48 ms 121684 KB Output is correct
6 Correct 54 ms 121680 KB Output is correct
7 Correct 49 ms 121732 KB Output is correct
8 Correct 49 ms 121680 KB Output is correct
9 Correct 50 ms 121676 KB Output is correct
10 Correct 49 ms 121680 KB Output is correct
11 Correct 52 ms 121676 KB Output is correct
12 Correct 47 ms 121680 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 121716 KB Output is correct
2 Correct 46 ms 121684 KB Output is correct
3 Correct 45 ms 121504 KB Output is correct
4 Correct 356 ms 130132 KB Output is correct
5 Correct 249 ms 129980 KB Output is correct
6 Correct 322 ms 127240 KB Output is correct
7 Correct 347 ms 127204 KB Output is correct
8 Correct 270 ms 127572 KB Output is correct
9 Correct 342 ms 127056 KB Output is correct
10 Correct 331 ms 126804 KB Output is correct
11 Correct 51 ms 121688 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 121684 KB Output is correct
2 Correct 49 ms 121680 KB Output is correct
3 Correct 49 ms 121692 KB Output is correct
4 Correct 49 ms 121680 KB Output is correct
5 Correct 61 ms 121728 KB Output is correct
6 Correct 50 ms 121532 KB Output is correct
7 Correct 49 ms 121600 KB Output is correct
8 Correct 51 ms 121680 KB Output is correct
9 Correct 48 ms 121688 KB Output is correct
10 Correct 49 ms 121652 KB Output is correct
11 Correct 49 ms 121676 KB Output is correct
12 Correct 580 ms 129876 KB Output is correct
13 Correct 869 ms 126288 KB Output is correct
14 Correct 220 ms 126804 KB Output is correct
15 Correct 1000 ms 126804 KB Output is correct
16 Correct 155 ms 126544 KB Output is correct
17 Correct 535 ms 127828 KB Output is correct
18 Correct 792 ms 127972 KB Output is correct
19 Correct 691 ms 128148 KB Output is correct
20 Correct 635 ms 127572 KB Output is correct
21 Correct 47 ms 121684 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 121680 KB Output is correct
2 Correct 48 ms 121684 KB Output is correct
3 Correct 49 ms 121568 KB Output is correct
4 Correct 50 ms 121684 KB Output is correct
5 Correct 49 ms 121520 KB Output is correct
6 Correct 48 ms 121684 KB Output is correct
7 Correct 49 ms 121548 KB Output is correct
8 Correct 48 ms 121684 KB Output is correct
9 Correct 50 ms 121684 KB Output is correct
10 Correct 50 ms 121584 KB Output is correct
11 Correct 49 ms 121684 KB Output is correct
12 Correct 366 ms 130128 KB Output is correct
13 Correct 283 ms 129812 KB Output is correct
14 Correct 347 ms 127316 KB Output is correct
15 Correct 370 ms 127060 KB Output is correct
16 Correct 263 ms 127568 KB Output is correct
17 Correct 357 ms 127244 KB Output is correct
18 Correct 327 ms 126720 KB Output is correct
19 Correct 569 ms 129836 KB Output is correct
20 Correct 842 ms 126292 KB Output is correct
21 Correct 207 ms 126788 KB Output is correct
22 Correct 980 ms 126668 KB Output is correct
23 Correct 153 ms 126548 KB Output is correct
24 Correct 505 ms 127832 KB Output is correct
25 Correct 770 ms 128064 KB Output is correct
26 Correct 695 ms 128084 KB Output is correct
27 Correct 647 ms 127572 KB Output is correct
28 Correct 334 ms 132692 KB Output is correct
29 Correct 822 ms 135252 KB Output is correct
30 Correct 2009 ms 129268 KB Output is correct
31 Correct 1883 ms 129396 KB Output is correct
32 Correct 353 ms 131408 KB Output is correct
33 Correct 486 ms 131400 KB Output is correct
34 Correct 174 ms 129184 KB Output is correct
35 Correct 607 ms 132692 KB Output is correct
36 Correct 1072 ms 133204 KB Output is correct
37 Correct 862 ms 133376 KB Output is correct
38 Correct 875 ms 132936 KB Output is correct
39 Correct 807 ms 133200 KB Output is correct
40 Correct 49 ms 121744 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 121660 KB Output is correct
2 Correct 53 ms 121680 KB Output is correct
3 Correct 53 ms 121680 KB Output is correct
4 Correct 47 ms 121684 KB Output is correct
5 Correct 46 ms 121496 KB Output is correct
6 Correct 44 ms 121680 KB Output is correct
7 Correct 45 ms 121684 KB Output is correct
8 Correct 44 ms 121680 KB Output is correct
9 Correct 44 ms 121684 KB Output is correct
10 Correct 43 ms 121576 KB Output is correct
11 Correct 44 ms 121684 KB Output is correct
12 Correct 353 ms 129980 KB Output is correct
13 Correct 236 ms 129784 KB Output is correct
14 Correct 323 ms 127432 KB Output is correct
15 Correct 369 ms 127104 KB Output is correct
16 Correct 261 ms 127568 KB Output is correct
17 Correct 353 ms 127056 KB Output is correct
18 Correct 321 ms 126804 KB Output is correct
19 Correct 605 ms 129804 KB Output is correct
20 Correct 852 ms 126260 KB Output is correct
21 Correct 220 ms 126804 KB Output is correct
22 Correct 1048 ms 126804 KB Output is correct
23 Correct 157 ms 126548 KB Output is correct
24 Correct 527 ms 127824 KB Output is correct
25 Correct 769 ms 128020 KB Output is correct
26 Correct 702 ms 128084 KB Output is correct
27 Correct 684 ms 127568 KB Output is correct
28 Correct 340 ms 132648 KB Output is correct
29 Correct 857 ms 135328 KB Output is correct
30 Correct 1992 ms 129080 KB Output is correct
31 Correct 1878 ms 129364 KB Output is correct
32 Correct 356 ms 131296 KB Output is correct
33 Correct 500 ms 131328 KB Output is correct
34 Correct 176 ms 129020 KB Output is correct
35 Correct 598 ms 132764 KB Output is correct
36 Correct 1047 ms 133208 KB Output is correct
37 Correct 873 ms 133456 KB Output is correct
38 Correct 746 ms 132944 KB Output is correct
39 Incorrect 214 ms 132900 KB Output isn't correct
40 Halted 0 ms 0 KB -