Submission #774183

#	Time	Username	Problem	Language	Result	Execution time	Memory
774183		alontanay	Game (IOI13_game)	C++14	100 / 100	5392 ms	73260 KiB

game

#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 __gcd(a, b);
}

template <typename T>
struct node {
    T val, gc;
    int prior;
    pi pos;
    node *l = nullptr, *r = nullptr;
    node(T v, pi pos) : val(v), gc(v), pos(pos), prior(rand()) {}
};

template <typename T>
using node_ptr = struct node<T> *;

template <typename T>
void print(node_ptr<T> 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);
}

template <typename T>
T gc(node_ptr<T> t) {
    return t ? t->gc : 0;
}
template <typename T>
void pull(node_ptr<T> t) {
    if (t) {
        t->gc = safe_gcd(t->val, safe_gcd(gc(t->l), gc(t->r)));
    }
}
template <typename T>
void merge(node_ptr<T> &t, node_ptr<T> l, node_ptr<T> 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);
}
template <typename T>
void split(node_ptr<T> t, node_ptr<T> &l, node_ptr<T> &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);
}
template <typename T>
void insert(node_ptr<T> &t, node_ptr<T> val) {
    node_ptr<T> 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;
}
template <typename T>
ll query(node_ptr<T> &t, pi a, pi b) {
    node_ptr<T> 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<ll> 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<ll>(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<ll> new_node = new node<ll>(k, pos);
        // cout << "~ INSERT " << l << " - " << r << endl;
        insert<ll>(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) { srand(time(0)); }
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 (stderr)

game.cpp: In instantiation of 'node<T>::node(T, pi) [with T = long long int; pi = std::pair<int, int>]':
game.cpp:126:52:   required from here
game.cpp:21:8: warning: 'node<long long int>::pos' will be initialized after [-Wreorder]
   21 |     pi pos;
      |        ^~~
game.cpp:20:9: warning:   'int node<long long int>::prior' [-Wreorder]
   20 |     int prior;
      |         ^~~~~
game.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     node(T v, pi pos) : val(v), gc(v), pos(pos), prior(rand()) {}
      |     ^~~~

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