oj.uz

Submission #1090809

# Submission time Handle Problem Language Result Execution time Memory
1090809 2024-09-18T19:33:03 Z vjudge1 Game (IOI13_game) C++17
100 / 100
 2287 ms 84048 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd() { return ((rng() % (1 << 15)) << 16) + (rng() % (1 << 15)); }

struct Node {
    ll pos, key, mn, mx;
    ll val, g;
    Node *l, *r;

    Node(int posi, ll vali) {
        l = r = nullptr;
        key = rnd();
        mn = mx = pos = posi;
        val = g = vali;
    }

    void update() {
        g = val;
        if(l) g = gcd(g, l->g);
        if(r) g = gcd(g, r->g);
        mn = (l ? l->mn : mn);
        mx = (r ? r->mx : mx);
    }
};

struct Treap {
    Node *root;

    Treap() { root = nullptr; }

    void split(Node *u, int x, Node *&l, Node *&r) {
        if(u == nullptr) {
            l = r = nullptr;
            return ;
        }

        if(u->pos < x) {
            split(u->r, x, l, r);
            u->r = l;
            l = u;
        } else {
            split(u->l, x, l, r);
            u->l = r;
            r = u;
        }

        u->update();
    }

    Node* merge(Node *l, Node *r) {
        if(!l || !r) return (l ? l : r);
        if(l->key < r->key) {
            l->r = merge(l->r, r);
            l->update();
            return l;
        } else {
            r->l = merge(l, r->l);
            r->update();
            return r;
        }
    }

    bool find(int id) {
        Node *u = root;
        while(u != nullptr) {
            if(u->pos == id) return 1;
            if(u->pos > id) {
                if(u->l == nullptr) return 0;
                u = u->l;
            }
            if(u->pos < id) {
                if(u->r == nullptr) return 0;
                u = u->r;
            }
        }
        return 0;
    }

    void update(Node *u, int p, ll v) {
        if(u->pos == p) {
            u->val = v;
            u->update();
            return ;
        }
        if(u->pos > p) update(u->l, p, v);
        else update(u->r, p, v);
        u->update();
    }

    void insert(int p, ll v) {
        // cerr  << "CALL " << p << " " << v << '\n';
        if(find(p)) {
            update(root, p, v);
            return ;
        }
        Node *l, *r;
        split(root, p, l, r);
        // cerr  << "test2\n";
        root = merge(merge(l, new Node(p, v)), r);
        // cerr  << "HA2\n";
    }

    ll query(Node *u, int tl, int tr) {
        if(u->mx < tl || tr < u->mn) return 0;
        if(tl <= u->mn && u->mx <= tr) return u->g;
        ll ans = (tl <= u->pos && u->pos <= tr ? u->val : 0);
        if(u->l) ans = gcd(ans, query(u->l, tl, tr));
        if(u->r) ans = gcd(ans, query(u->r, tl, tr));
        return ans;
    }

    ll query(int tl, int tr) { return (root ? query(root, tl, tr) : 0); }
};

struct SegTree {
    SegTree *l, *r;
    Treap t;
    int L, R;

    SegTree() { l = r = nullptr; }
    SegTree(int a, int b) : L(a), R(b), l(nullptr), r(nullptr) {}

    int tm() { return (L + R) / 2; }
    void add_l() { if(!l) l = new SegTree(L, tm()); }
    void add_r() { if(!r) r = new SegTree(tm()+1, R); }

    void merge(int p) {
        ll ans = 0;
        if(l) ans = gcd(ans, l->t.query(p, p));
        if(r) ans = gcd(ans, r->t.query(p, p));
        t.insert(p, ans);
    }

    void update(int x, int y, ll val) {
        if(x < L || R < x) return ;
        // cerr  << L << " " << R  << '\n';
        if(L == R) {
            t.insert(y, val);
            return ;
        }

        if(x <= tm()) {
            add_l();
            l->update(x, y, val);
        } else {
            add_r();
            r->update(x, y, val);
        }
        // cerr  << "HERE\n";
        merge(y);
    }

    ll query(int x1, int x2, int y1, int y2) {
        if(x2 < L || R < x1) return 0;
        if(x1 <= L && R <= x2) return t.query(y1, y2);

        ll ans = 0;
        if(l) ans = gcd(ans, l->query(x1, x2, y1, y2));
        if(r) ans = gcd(ans, r->query(x1, x2, y1, y2));
        return ans;
    }
};

SegTree tree;

void init(int R, int C) {
    tree = SegTree(0, R-1);
}

void update(int P, int Q, ll K) {
    tree.update(P, Q, K);
    // cerr  << "HA\n";
}

ll calculate(int P, int Q, int U, int V) {
    return tree.query(P, U, Q, V);
}

Compilation message

game.cpp: In constructor 'SegTree::SegTree(int, int)':
game.cpp:132:12: warning: 'SegTree::R' will be initialized after [-Wreorder]
  132 |     int L, R;
      |            ^
game.cpp:130:14: warning:   'SegTree* SegTree::l' [-Wreorder]
  130 |     SegTree *l, *r;
      |              ^
game.cpp:135:5: warning:   when initialized here [-Wreorder]
  135 |     SegTree(int a, int b) : L(a), R(b), l(nullptr), r(nullptr) {}
      |     ^~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 383 ms 11968 KB Output is correct
5 Correct 185 ms 11860 KB Output is correct
6 Correct 466 ms 9556 KB Output is correct
7 Correct 529 ms 9048 KB Output is correct
8 Correct 314 ms 7760 KB Output is correct
9 Correct 517 ms 9304 KB Output is correct
10 Correct 509 ms 8940 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 591 ms 14672 KB Output is correct
13 Correct 818 ms 8356 KB Output is correct
14 Correct 166 ms 5716 KB Output is correct
15 Correct 866 ms 9964 KB Output is correct
16 Correct 180 ms 13020 KB Output is correct
17 Correct 659 ms 10664 KB Output is correct
18 Correct 1189 ms 14248 KB Output is correct
19 Correct 1027 ms 14592 KB Output is correct
20 Correct 1042 ms 13876 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 414 ms 11996 KB Output is correct
13 Correct 174 ms 11860 KB Output is correct
14 Correct 484 ms 9488 KB Output is correct
15 Correct 522 ms 9008 KB Output is correct
16 Correct 333 ms 7668 KB Output is correct
17 Correct 547 ms 9296 KB Output is correct
18 Correct 520 ms 8784 KB Output is correct
19 Correct 574 ms 14668 KB Output is correct
20 Correct 824 ms 8272 KB Output is correct
21 Correct 146 ms 5716 KB Output is correct
22 Correct 879 ms 9892 KB Output is correct
23 Correct 178 ms 12884 KB Output is correct
24 Correct 673 ms 10528 KB Output is correct
25 Correct 1202 ms 14440 KB Output is correct
26 Correct 1020 ms 14420 KB Output is correct
27 Correct 1000 ms 13876 KB Output is correct
28 Correct 297 ms 43816 KB Output is correct
29 Correct 961 ms 46540 KB Output is correct
30 Correct 1124 ms 34128 KB Output is correct
31 Correct 976 ms 27732 KB Output is correct
32 Correct 216 ms 10320 KB Output is correct
33 Correct 312 ms 10756 KB Output is correct
34 Correct 298 ms 40308 KB Output is correct
35 Correct 864 ms 27648 KB Output is correct
36 Correct 1610 ms 44368 KB Output is correct
37 Correct 1334 ms 44676 KB Output is correct
38 Correct 1376 ms 44164 KB Output is correct
39 Correct 1105 ms 36692 KB Output is correct
40 Correct 1 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 399 ms 12012 KB Output is correct
13 Correct 166 ms 11856 KB Output is correct
14 Correct 463 ms 9492 KB Output is correct
15 Correct 517 ms 9232 KB Output is correct
16 Correct 302 ms 7684 KB Output is correct
17 Correct 555 ms 9296 KB Output is correct
18 Correct 510 ms 8788 KB Output is correct
19 Correct 562 ms 14588 KB Output is correct
20 Correct 834 ms 8276 KB Output is correct
21 Correct 146 ms 5712 KB Output is correct
22 Correct 829 ms 9936 KB Output is correct
23 Correct 180 ms 12888 KB Output is correct
24 Correct 681 ms 10584 KB Output is correct
25 Correct 1189 ms 14420 KB Output is correct
26 Correct 1012 ms 14420 KB Output is correct
27 Correct 1028 ms 13820 KB Output is correct
28 Correct 301 ms 43860 KB Output is correct
29 Correct 954 ms 46684 KB Output is correct
30 Correct 1084 ms 34120 KB Output is correct
31 Correct 939 ms 27724 KB Output is correct
32 Correct 215 ms 10196 KB Output is correct
33 Correct 324 ms 10740 KB Output is correct
34 Correct 260 ms 40208 KB Output is correct
35 Correct 842 ms 27732 KB Output is correct
36 Correct 1614 ms 44372 KB Output is correct
37 Correct 1340 ms 44624 KB Output is correct
38 Correct 1354 ms 44084 KB Output is correct
39 Correct 415 ms 82004 KB Output is correct
40 Correct 1750 ms 84048 KB Output is correct
41 Correct 1686 ms 64684 KB Output is correct
42 Correct 1574 ms 50532 KB Output is correct
43 Correct 537 ms 78804 KB Output is correct
44 Correct 306 ms 10576 KB Output is correct
45 Correct 1150 ms 36616 KB Output is correct
46 Correct 2279 ms 82856 KB Output is correct
47 Correct 2287 ms 82772 KB Output is correct
48 Correct 2279 ms 82236 KB Output is correct
49 Correct 1 ms 344 KB Output is correct