제출 #580092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580092		MohamedFaresNebili	게임 (IOI13_game)	C++14	63 / 100	1641 ms	256000 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;

        ll R, C;
        struct X{
            X *lf, *rf; ll l, r; ll res;
            X(ll s, ll 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, ll p, ll k) {
            int l = v -> l, r = v -> r;
            if(l == r) {
                v -> res = k;
                return;
            }
            ll md = (l + r) / 2;
            if(p <= md) {
                if(!v -> lf) v -> lf = new X(l, md);
                update(v -> lf, p, k);
            }
            else {
                if(!v -> rf) v -> rf = new X(md + 1, r);
                update(v -> rf, p, k);
            }
            v -> res = op(v -> lf ? v -> lf -> res : 0,
                          v -> rf ? v -> rf -> res : 0);
        }


        ll query(X *v, ll l, ll 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));
        }
        ll query(Y* V, ll l, ll r, ll p, ll q, ll u, ll v) {
            if(!V || l > u || r < p) return 0;
            if(l >= p && r <= u) return query(&V -> node, q, v);
            ll 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));
        }

        void update(Y *v, ll l, ll r, ll x, ll y, ll k) {
            ll 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);
        }

        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);
        }

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In constructor 'X::X(ll, ll)':
game.cpp:21:31: warning: 'X::r' will be initialized after [-Wreorder]
   21 |             X *lf, *rf; ll l, r; ll res;
      |                               ^
game.cpp:21:16: warning:   'X* X::lf' [-Wreorder]
   21 |             X *lf, *rf; ll l, r; ll res;
      |                ^~
game.cpp:22:13: warning:   when initialized here [-Wreorder]
   22 |             X(ll s, ll 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: 0 / 17
• Subtask 5: 0 / 20