Submission #330925

#	Time	Username	Problem	Language	Result	Execution time	Memory
330925		smax	Game (IOI13_game)	C++17	100 / 100	7661 ms	47076 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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 Node {
    int key, priority;
    long long val, ans;
    Node *l, *r;

    Node(int _key, long long _val) : key(_key), priority(rand() + (rand() << 15)), val(_val), ans(_val), l(NULL), r(NULL) {}
};
typedef Node* pNode;

long long ans(pNode t) {
    return t ? t->ans : 0;
}

void pull(pNode t) {
    if (t) t->ans = gcd2(gcd2(ans(t->l), ans(t->r)), t->val);
}

void split(pNode t, int key, pNode &l, pNode &r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split(t->l, key, l, t->l), r = t;
    else
        split(t->r, key, t->r, r), l = t;
    pull(t);
}

void merge(pNode &t, pNode l, pNode r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->priority > r->priority)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;
    pull(t);
}

long long query(pNode t, int l, int r) {
    pNode pl, pm, pr;
    split(t, l-1, pl, pm);
    split(pm, r, t, pr);
    long long ret = ans(t);
    merge(pm, pl, t);
    merge(t, pm, pr);
    return ret;
}

void update(pNode &t, int p, long long val) {
    pNode pl, pm, pr;
    split(t, p-1, pl, pm);
    split(pm, p, t, pr);
    if (t) t->val = t->ans = val;
    else t = new Node(p, val);
    merge(pm, pl, t);
    merge(t, pm, pr);
}

struct Seg {
    pNode node;
    Seg *l, *r;

    Seg() : node(NULL), l(NULL), r(NULL) {}
};

int n, _r;

long long query(Seg *p, int l, int r, int ix, int iy, int jx, int jy) {
    if (ix > r || jx < l || !p)
        return 0;
    if (ix <= l && r <= jx)
        return query(p->node, iy, jy);
    int m = (l + r) / 2;
    return gcd2(query(p->l, l, m, ix, iy, jx, jy), query(p->r, m+1, r, ix, iy, jx, jy));
}

void update(Seg *p, int l, int r, int x, int y, long long val) {
    if (l == r) {
        update(p->node, y, val);
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        if (!p->l) p->l = new Seg();
        update(p->l, l, m, x, y, val);
    } else {
        if (!p->r) p->r = new Seg();
        update(p->r, m+1, r, x, y, val);
    }
    update(p->node, y, gcd2(p->l ? query(p->l->node, y, y) : 0, p->r ? query(p->r->node, y, y) : 0));
}

Seg st;

void init(int R, int C) {
    n = C;
    _r = R;
}

void update(int P, int Q, long long K) {
    update(&st, 0, _r-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, 0, _r-1, P, Q, U, V);
}

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