Submission #580103

#	Time	Username	Problem	Language	Result	Execution time	Memory
580103		MohamedFaresNebili	게임 (IOI13_game)	C++14	100 / 100	3024 ms	82088 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int R, C;
        struct X{
            X *lf, *rf; int l, r; ll res;
            X(int s, int e): l(s), r(e), lf(nullptr), rf(nullptr), res(0ll) {}
        };
        struct Y{
            Y *lf, *rf; X node;
            Y(): lf(nullptr), rf(nullptr), node(0, C - 1) {}
        };

        ll op(ll A, ll B) {
            return __gcd(A, B);
        }
        void update(X *v, int p, ll k) {
            int l = v -> l, r = v -> r;
            if(l == r) {
                v -> res = k;
                return;
            }
            int md = (l + r) / 2;
            X **to = &(p <= md ? v -> lf : v -> rf);
            if(!*to) {
                *to = new X(p, p);
                (*to) -> res = k;
            }
            else if((*to) -> l <= p && (*to) -> r >= p)
                update(*to, p, k);
            else {
                while((p <= md) == ((*to) -> l <= md)) {
                    if(p <= md) r = md;
                    else l = md + 1;
                    md = (l + r) / 2;
                }
                X *node = new X(l, r);
                if((*to) -> r <= md) node -> lf = *to;
                else node -> rf = *to;
                *to = node;
                update(*to, p, k);
            }
            v -> res = op(v -> lf ? v -> lf -> res : 0,
                          v -> rf ? v -> rf -> res : 0);
        }

        ll query(X *v, int l, int r) {
            if(!v || v -> l > r || v -> r < l) return 0ll;
            if(v -> l >= l && v -> r <= r) return v -> res;
            return op(query(v -> lf, l, r), query(v -> rf, l, r));
        }

        void update(Y *v, int l, int r, int x, int y, ll k) {
            int md = (l + r) / 2;
            if(l == r) {
                update(&v -> node, y, k);
                return;
            }
            if(x <= md) {
                if(!v -> lf) v -> lf = new Y();
                update(v -> lf, l, md, x, y, k);
            }
            else {
                if(!v -> rf) v -> rf = new Y();
                update(v -> rf, md + 1, r, x, y, k);
            }
            ll curr = op(
                v -> lf ? query(&v -> lf -> node, y, y) : 0,
                v -> rf ? query(&v -> rf -> node, y, y) : 0);
            update(&v -> node, y, curr);
        }

        ll query(Y* V, int l, int r, int p, int q, int u, int v) {
            if(!V || l > u || r < p) return 0;
            if(l >= p && r <= u) return query(&V -> node, q, v);
            int md = (l + r) / 2;
            return op(query(V -> lf, l, md, p, q, u, v),
                      query(V -> rf, md + 1, r, p, q, u, v));
        }

        Y* root;
        void init(int N, int M) {
            R = N, C = M;
            root = new Y();
        }
        void update(int P, int Q, ll K) {
            update(root, 0, R - 1, P, Q, K);
        }
        ll calculate(int P, int Q, int U, int V) {
            return query(root, 0, R - 1, P, Q, U, V);
        }

Compilation message (stderr)

game.cpp: In constructor 'X::X(int, int)':
game.cpp:21:32: warning: 'X::r' will be initialized after [-Wreorder]
   21 |             X *lf, *rf; int l, r; ll res;
      |                                ^
game.cpp:21:16: warning:   'X* X::lf' [-Wreorder]
   21 |             X *lf, *rf; int l, r; ll res;
      |                ^~
game.cpp:22:13: warning:   when initialized here [-Wreorder]
   22 |             X(int s, int e): l(s), r(e), lf(nullptr), rf(nullptr), res(0ll) {}
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20