Submission #554506

#	Time	Username	Problem	Language	Result	Execution time	Memory
554506		elazarkoren	Game (IOI13_game)	C++17	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

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

const int infinity = 1e9;

mt19937 rng(time(0));
auto Dist = uniform_int_distribution<int>(0, infinity);

inline int mrand() {
    return Dist(rng);
}

struct Node {
    int index = 0;
    ll val = 0, gcd = 0;
    int prio;
    Node *l = 0, *r = 0;
    Node(int i, ll x): index(i), val(x), gcd(x), prio(mrand()) {}
    inline void pull() {
        gcd = gcd2(val, gcd2(l ? l->gcd : 0, r ? r->gcd : 0));
    }
};
typedef Node* pnode;

void Merge(pnode &t, pnode l, pnode r) {
    if (!l || !r) {
        t = l ? l : r;
        return;
    }
    if (l->prio > r->prio) {
        t = l;
        Merge(t->l, l->r, r);
    } else {
        t = r;
        Merge(t->l, l, r->l);
    }
    t->pull();
}

void Split(pnode t, pnode &l, pnode &r, int ind) { // <= ind
    if (!t) {
        l = r = t;
        return;
    }
    if (t->index <= ind) {
        l = t;
        Split(t->r, l->r, r, ind);
    } else {
        r = t;
        Split(t->l, l, r->l, ind);
    }
    if (l) l->pull();
    if (r) r->pull();
}

struct Treap {
    pnode t = 0;
    void insert(int i, ll x) {
        pnode l, r, mid;
        Split(t, l, r, i - 1);
        Split(r, mid, r, i);
        if (mid) delete mid;
        Merge(t, l, new Node(i, x));
        Merge(t, t, r);
    }
    ll query(int a, int b) {
        pnode l, r, mid;
        Split(t, l, r, b - 1);
        Split(l, l, mid, a - 1);
        ll x = mid ? mid->gcd : 0;
        Merge(t, l, mid);
        Merge(t, t, r);
        return x;
    }
};

struct Seg {
    int n;
    vector<Treap> seg;
    Seg () {}
    Seg (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
    }
    void update(int i, int j, ll x) {
        i += n;
        seg[i].insert(j, x);
        for (i >>= 1; i; i >>= 1) {
            x = gcd2(seg[i << 1].query(j, j + 1), seg[i << 1 | 1].query(j, j + 1));
            seg[i].insert(j, x);
        }
    }
    ll query(int x1, int y1, int x2, int y2) {
        ll ans = 0;
        for (x1 += n, x2 += n; x1 < x2; x1 >>= 1, x2 >>= 1) {
            if (x1 & 1) ans = gcd2(ans, seg[x1++].query(y1, y2));
            if (x2 & 1) ans = gcd2(ans, seg[--x2].query(y1, y2));
        }
        return ans;
    }
};

int n, m;
Seg seg;

void init(int R, int C) {
    n = R, m = C;
    seg = Seg(n);
}

void update(int p, int q, long long k) {
    seg.update(p, q, k);
}

long long calculate(int p, int q, int u, int v) {
    return seg.query(p, q, u + 1, v + 1);
}

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