oj.uz

Submission #774227

# Submission time Handle Problem Language Result Execution time Memory
774227 2023-07-05T13:14:04 Z alontanay Game (IOI13_game) C++14
100 / 100
 5865 ms 73212 KB 
#include "game.h"

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using pi = pair<int, int>;

ll safe_gcd(ll a, ll b) {
    if (a == 0 || b == 0) {
        return a + b;
    }
    return safe_gcd(b, a % b);
}

mt19937 rng;

typedef struct node *node_ptr;
struct node {
    ll val, gc;
    int prior;
    pi pos;
    node *l = nullptr, *r = nullptr;
    node(ll v, pi pos)
        : val(v),
          gc(v),
          pos(pos),
          prior(uniform_int_distribution<int>(0, 1e9)(rng)) {}
};

void print(node_ptr t, int id = 0) {
    for (int i = 0; i < id; i++) {
        cout << "  ";
    }
    if (!t) {
        cout << "-" << endl;
        return;
    }
    cout << t->val << endl;
    print(t->l, id + 1);
    print(t->r, id + 1);
}

ll gc(node_ptr t) { return t ? t->gc : 0; }
void pull(node_ptr t) {
    if (t) {
        t->gc = safe_gcd(t->val, safe_gcd(gc(t->l), gc(t->r)));
    }
}
void merge(node_ptr &t, node_ptr l, node_ptr r) {
    if (!l || !r) {
        t = l ? l : r;
        return;
    }
    if (l->prior > r->prior) {
        merge(l->r, l->r, r);
        t = l;
    } else {
        merge(r->l, l, r->l);
        t = r;
    }
    pull(t);
}
void split(node_ptr t, node_ptr &l, node_ptr &r, pi key) {
    if (!t) {
        return void(l = r = 0);
    }
    if (t->pos >= key) {
        split(t->l, l, t->l, key);
        r = t;
    } else {
        split(t->r, t->r, r, key);
        l = t;
    }
    pull(t);
}
void insert(node_ptr &t, node_ptr val) {
    node_ptr l = nullptr, m = nullptr, r = nullptr;
    // cout << "A" << endl;
    split(t, l, r, val->pos);
    // cout << "B" << endl;
    split(r, m, r, {val->pos.f, val->pos.s + 1});
    m = val;
    // cout << "D" << endl;
    merge(r, m, r);
    // cout << "X" << endl;
    // cout << gc(l) << " " << gc(r) << " " << gc(t) << endl;
    merge(t, l, r);
    // cout << "A" << endl;
}

ll query(node_ptr &t, pi a, pi b) {
    node_ptr l = nullptr, m = nullptr, r = nullptr;
    split(t, m, r, b);
    split(m, l, m, a);
    // print(m);
    ll res = gc(m);
    merge(m, l, m);
    merge(t, m, r);
    return res;
}

struct SegTreap {
    node_ptr val = nullptr;
    int l, r, mid;
    SegTreap *ls, *rs;
    SegTreap(int l, int r) : l(l), r(r), mid((l + r) / 2) {}
    ll query_rect(int a, int b, int c, int d) {
        // cout << "~ QUERY" << endl;
        if (a >= r || b <= l) {
            return 0;
        }
        if (a <= l && b >= r) {
            return query(val, {c, a}, {d - 1, b});
        }
        return safe_gcd(ls ? ls->query_rect(a, b, c, d) : 0,
                        rs ? rs->query_rect(a, b, c, d) : 0);
    }
    void update(int a, pi pos, ll k) {
        node_ptr new_node = new node(k, pos);
        // cout << "~ INSERT " << l << " - " << r << endl;
        insert(val, new_node);
        // cout << "DONE" << endl;
        // print(val);
        if (l + 1 == r) {
            return;
        }
        if (a < mid) {
            if (!ls) {
                ls = new SegTreap(l, mid);
            }
            ls->update(a, pos, k);
        } else {
            if (!rs) {
                rs = new SegTreap(mid, r);
            }
            rs->update(a, pos, k);
        }
    }
};

const int INF = 1e9 + 1;
SegTreap seg2d(0, INF);
void init(int R, int C) {
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
}
void update(int P, int Q, long long K) {
    // cout << "ADD " << P << " " << Q << " " << K << endl;
    seg2d.update(P, {Q, P}, K);
}
long long calculate(int P, int Q, int U, int V) {
    // cout << "CALC " << P << " " << Q << " " << U << " " << V << endl;
    return seg2d.query_rect(P, U + 1, Q, V + 1);
}

Compilation message

game.cpp: In constructor 'node::node(ll, pi)':
game.cpp:23:8: warning: 'node::pos' will be initialized after [-Wreorder]
   23 |     pi pos;
      |        ^~~
game.cpp:22:9: warning:   'int node::prior' [-Wreorder]
   22 |     int prior;
      |         ^~~~~
game.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     node(ll v, pi pos)
      |     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1043 ms 28028 KB Output is correct
5 Correct 619 ms 27816 KB Output is correct
6 Correct 1536 ms 25184 KB Output is correct
7 Correct 1690 ms 25132 KB Output is correct
8 Correct 954 ms 15344 KB Output is correct
9 Correct 1610 ms 25124 KB Output is correct
10 Correct 1370 ms 24676 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1137 ms 27264 KB Output is correct
13 Correct 2573 ms 24384 KB Output is correct
14 Correct 626 ms 24780 KB Output is correct
15 Correct 2744 ms 24932 KB Output is correct
16 Correct 843 ms 24716 KB Output is correct
17 Correct 1648 ms 15796 KB Output is correct
18 Correct 2922 ms 26192 KB Output is correct
19 Correct 2563 ms 26332 KB Output is correct
20 Correct 2322 ms 25708 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 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 2 ms 472 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1008 ms 28004 KB Output is correct
13 Correct 580 ms 27860 KB Output is correct
14 Correct 1437 ms 25208 KB Output is correct
15 Correct 1595 ms 25052 KB Output is correct
16 Correct 910 ms 15404 KB Output is correct
17 Correct 1571 ms 25096 KB Output is correct
18 Correct 1405 ms 24716 KB Output is correct
19 Correct 1212 ms 27900 KB Output is correct
20 Correct 2715 ms 24376 KB Output is correct
21 Correct 633 ms 24880 KB Output is correct
22 Correct 2796 ms 24884 KB Output is correct
23 Correct 920 ms 24692 KB Output is correct
24 Correct 1627 ms 15828 KB Output is correct
25 Correct 3070 ms 26180 KB Output is correct
26 Correct 2551 ms 26336 KB Output is correct
27 Correct 2414 ms 25700 KB Output is correct
28 Correct 789 ms 39008 KB Output is correct
29 Correct 1509 ms 41688 KB Output is correct
30 Correct 3796 ms 31712 KB Output is correct
31 Correct 3309 ms 30820 KB Output is correct
32 Correct 606 ms 29336 KB Output is correct
33 Correct 959 ms 29456 KB Output is correct
34 Correct 1047 ms 35456 KB Output is correct
35 Correct 1585 ms 25188 KB Output is correct
36 Correct 2984 ms 39536 KB Output is correct
37 Correct 2325 ms 39732 KB Output is correct
38 Correct 2400 ms 39188 KB Output is correct
39 Correct 2064 ms 32948 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 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1095 ms 27972 KB Output is correct
13 Correct 615 ms 27876 KB Output is correct
14 Correct 1451 ms 25300 KB Output is correct
15 Correct 1603 ms 25016 KB Output is correct
16 Correct 925 ms 15428 KB Output is correct
17 Correct 1569 ms 25000 KB Output is correct
18 Correct 1376 ms 24764 KB Output is correct
19 Correct 1164 ms 27876 KB Output is correct
20 Correct 2705 ms 24388 KB Output is correct
21 Correct 636 ms 24836 KB Output is correct
22 Correct 2813 ms 24948 KB Output is correct
23 Correct 822 ms 24728 KB Output is correct
24 Correct 1618 ms 15756 KB Output is correct
25 Correct 2961 ms 26188 KB Output is correct
26 Correct 2595 ms 26488 KB Output is correct
27 Correct 2391 ms 25696 KB Output is correct
28 Correct 775 ms 39008 KB Output is correct
29 Correct 1433 ms 41624 KB Output is correct
30 Correct 3743 ms 31736 KB Output is correct
31 Correct 3190 ms 30956 KB Output is correct
32 Correct 594 ms 29364 KB Output is correct
33 Correct 959 ms 29388 KB Output is correct
34 Correct 1106 ms 35480 KB Output is correct
35 Correct 1594 ms 25476 KB Output is correct
36 Correct 2882 ms 39784 KB Output is correct
37 Correct 2314 ms 39744 KB Output is correct
38 Correct 2269 ms 39216 KB Output is correct
39 Correct 1095 ms 71236 KB Output is correct
40 Correct 2440 ms 73212 KB Output is correct
41 Correct 5865 ms 60344 KB Output is correct
42 Correct 5216 ms 57964 KB Output is correct
43 Correct 1485 ms 67980 KB Output is correct
44 Correct 1113 ms 52980 KB Output is correct
45 Correct 1989 ms 32928 KB Output is correct
46 Correct 3747 ms 71988 KB Output is correct
47 Correct 3636 ms 71972 KB Output is correct
48 Correct 3410 ms 71684 KB Output is correct
49 Correct 1 ms 212 KB Output is correct