Submission #774227

#	Time	Username	Problem	Language	Result	Execution time	Memory
774227		alontanay	Game (IOI13_game)	C++14	100 / 100	5865 ms	73212 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 safe_gcd(b, a % b);
}

mt19937 rng;

typedef struct node *node_ptr;
struct node {
    ll val, gc;
    int prior;
    pi pos;
    node *l = nullptr, *r = nullptr;
    node(ll v, pi pos)
        : val(v),
          gc(v),
          pos(pos),
          prior(uniform_int_distribution<int>(0, 1e9)(rng)) {}
};

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

ll gc(node_ptr t) { return t ? t->gc : 0; }
void pull(node_ptr t) {
    if (t) {
        t->gc = safe_gcd(t->val, safe_gcd(gc(t->l), gc(t->r)));
    }
}
void merge(node_ptr &t, node_ptr l, node_ptr 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);
}
void split(node_ptr t, node_ptr &l, node_ptr &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);
}
void insert(node_ptr &t, node_ptr val) {
    node_ptr 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;
}

ll query(node_ptr &t, pi a, pi b) {
    node_ptr 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 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(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 new_node = new node(k, pos);
        // cout << "~ INSERT " << l << " - " << r << endl;
        insert(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) {
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
}
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 constructor 'node::node(ll, pi)':
game.cpp:23:8: warning: 'node::pos' will be initialized after [-Wreorder]
   23 |     pi pos;
      |        ^~~
game.cpp:22:9: warning:   'int node::prior' [-Wreorder]
   22 |     int prior;
      |         ^~~~~
game.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     node(ll v, pi pos)
      |     ^~~~

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