Submission #925405

#	Time	Username	Problem	Language	Result	Execution time	Memory
925405		BestCrazyNoob	Game (IOI13_game)	C++14	0 / 100	0 ms	348 KiB

game

#include "game.h"
#include <random>
#include <utility>
#include <string.h>

using namespace std;
using ll = long long;

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

struct treap {
    treap *L, *R;
    int key, pri;
    ll val, res;
    treap(int i, ll x): key(i), pri(rand()), val(x), res(x), L(nullptr), R(nullptr) {}
    treap *join(treap *L, treap *R) {
        this->L = L;
        this->R = R;
        res = gcd2(val, gcd2(L ? L->res : 0, R ? R->res : 0));
        return this;
    }
};

treap* merge(treap *L, treap *R) {
    if (!L) return R;
    if (!R) return L;
    if (L->pri > R->pri) {
        return L->join(L->L, merge(L->R, R));
    } else {
        return R->join(merge(L, R->L), R->R);
    }
}

pair<treap*, treap*> split(treap *T, int x) {
    if (!T) return {nullptr, nullptr};
    if (x <= T->key) {
        auto [LL, LR] = split(T->L, x);
        return {LL, T->join(LR, T->R)};
    } else {
        auto [RL, RR] = split(T->R, x);
        return {T->join(T->L, RL), RR};
    }
}

treap* insert(treap *T, int i, ll x) {
    auto [L, R] = split(T, i);
    return merge(L, merge(new treap(i, x), R));
}

// incl - excl
ll query(treap *T, int l, int r) {
    auto [L, R] = split(T, l);
    auto [RL, RR] = split(R, r);
    ll res = RL ? RL->res : 0;
    T = merge(L, merge(RL, RR));
    return res;
}

// sparse segment tree
struct node {
    node *L, *R;
    treap *val;
    node(): L(nullptr), R(nullptr), val(nullptr) {}
};

struct segtree {
    node *root;
    int sz;
    int ql, qr, qx, qy;
    ll qk;
    segtree() {}
    segtree(int N) {
        sz = 1;
        while (sz < N) sz *= 2;
        root = new node();
    }
    void push(node *nd) {
        if (!nd->L) nd->L = new node();
        if (!nd->R) nd->R = new node();
    }
    ll __query(node *nd, int nl, int nr) {
        if (qr <= nl || nr <= ql || nd == nullptr) return 0;
        if (ql <= nl && nr <= qr) return ::query(nd->val, qx, qy);
        int nm = (nl+nr)/2;
        return gcd2(__query(nd->L, nl, nm), __query(nd->R, nm, nr));
    }
    ll query(int l, int r, int x, int y) {
        ql = l; qr = r; qx = x; qy = y;
        return __query(root, 0, sz);
    }
    void __upd(node *nd, int nl, int nr) {
        if (ql < nl || nr <= ql) return;
        nd->val = insert(nd->val, qx, qk);
        if (nl+1 == nr) return;
        push(nd);
        int nm = (nl+nr)/2;
        __upd(nd->L, nl, nm);
        __upd(nd->R, nm, nr);
    }
    void upd(int l, int x, ll k) {
        ql = l; qx = x; qk = k;
        __upd(root, 0, sz);
    }
};

segtree seg;

void init(int R, int C) {
    seg = segtree(R);
}

void update(int P, int Q, long long K) {
    seg.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    // P, U: rows
    // Q, V: columns
    return seg.query(P, U+1, Q, V+1);
}

Compilation message (stderr)

game.cpp: In constructor 'treap::treap(int, ll)':
game.cpp:22:13: warning: 'treap::res' will be initialized after [-Wreorder]
   22 |     ll val, res;
      |             ^~~
game.cpp:20:12: warning:   'treap* treap::L' [-Wreorder]
   20 |     treap *L, *R;
      |            ^
game.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     treap(int i, ll x): key(i), pri(rand()), val(x), res(x), L(nullptr), R(nullptr) {}
      |     ^~~~~
game.cpp: In function 'std::pair<treap*, treap*> split(treap*, int)':
game.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [LL, LR] = split(T->L, x);
      |              ^
game.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [RL, RR] = split(T->R, x);
      |              ^
game.cpp: In function 'treap* insert(treap*, int, ll)':
game.cpp:54:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     auto [L, R] = split(T, i);
      |          ^
game.cpp: In function 'll query(treap*, int, int)':
game.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     auto [L, R] = split(T, l);
      |          ^
game.cpp:61:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     auto [RL, RR] = split(R, r);
      |          ^

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