Submission #930104

#	Time	Username	Problem	Language	Result	Execution time	Memory
930104		hoangsacura	Game (IOI13_game)	C++17	100 / 100	5693 ms	63652 KiB

game

#include<bits/stdc++.h>
#include "game.h"
#define task ""
#define PI acos(-1)
#define fi first
#define sc second
#define ll long long
#define ld long double
#define rep(i, a, b, c) for (int i = a; i <= b; i += c)
#define ford(i, a, b, c) for (int i = a; i >= b; i -= c)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int inf = 2e9, bsize = 350, maxn = 1e6 + 2, N = 2e5, mod = 998224353;
const long long llinf = 1e18;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef pair<II, II> IV;
int R, C;

struct Node {
    Node *left, *right, *par;
    int pos = 0;
    ll val = 0;
    ll GCD = 0;
};

typedef Node* tnode;
tnode nilt;

void upnode(tnode x) {
    x->GCD = __gcd(x->left->GCD, __gcd(x->right->GCD, x->val));
}

void link(tnode x, tnode y, bool left) {
    y->par = x;

    if (left)
        x->left = y;
    else
        x->right = y;
}

void uptree(tnode x) {
    tnode y = x->par;
    tnode z = y->par;

    if (y->left == x) {
        link(y, x->right, 1);
        link(x, y, 0);
    }
    else {
        link(y, x->left, 0);
        link(x, y, 1);
    }

    if (z != nilt) {
        if (z->left == y)
            link(z, x, 1);
        else
            link(z, x, 0);
    }
    else
        x->par = z;

    upnode(y);
    upnode(x);
}

void splay(tnode x) {
    if (x == nilt)
        return;

    while (x->par != nilt) {
        tnode y = x->par;
        tnode z = y->par;

        if (z != nilt) {
            if ((z->left == y) == (y->left == x))
                uptree(y);
            else
                uptree(x);
        }
        uptree(x);
    }
}

tnode Find(tnode &t, int pos) {
    if (t == nilt)
        return t;

    tnode res = nilt;
    tnode x = t;

    while (x != nilt) {
        t = x;

        if (pos < x->pos)
            x = x->left;
        else {
            res = x;
            x = x->right;
        }
    }

    splay(t);

    return res;
}

void split(tnode T, int pos, tnode &T1, tnode &T2) {
    T1 = Find(T, pos);

    if (T1 == nilt)
        T2 = T;
    else {
        splay(T1);
        T2 = T1->right;
        T1->right = T2->par = nilt;
        upnode(T1);
    }
}

tnode join(tnode T1, tnode T2) {
    if (T1 == nilt)
        return T2;

    while (T1->right != nilt)
        T1 = T1->right;
    splay(T1);

    if (T2 != nilt)
        link(T1, T2, 0);

    upnode(T1);

    return T1;
}

void ins(tnode &root, int pos, ll val) {
    if (root == nilt) {
        root = new Node();
        root->left = root->right = root->par = nilt;
        root->pos = pos;
        root->val = root->GCD = val;
        return;
    }

    tnode p = Find(root, pos);

    if (p == nilt) {
        tnode x = root;
        root = new Node();
        root->left = root->right = root->par = nilt;
        root->pos = pos;
        root->val = val;

        link(root, x, 0);

        upnode(root);

        return;
    }

    root = p;
    splay(root);

    if (p->pos < pos) {
        tnode x, y;
        x = root;
        y = x->right;
        y->par = x->right = nilt;
        upnode(x);

        root = new Node();
        root->left = root->right = root->par = nilt;
        root->pos = pos;
        root->val = val;

        if (x != nilt)
            link(root, x, 1);
        if (y != nilt)
            link(root, y, 0);

        upnode(root);

        return;
    }

    root->val = val;
    upnode(root);
}

ll take(tnode &root, int pos) {
    tnode p = Find(root, pos);

    if (p == nilt || p->pos != pos)
        return 0;

    return p->val;
}

struct IT {
    tnode x;
    int left = -1;
    int right = -1;
};
vector<IT> it;

void up(int r, int Q) {
    ll Left = (it[r].left == -1) ? 0 : take(it[it[r].left].x, Q);
    ll Right = (it[r].right == -1) ? 0 : take(it[it[r].right].x, Q);
    ins(it[r].x, Q, __gcd(Left, Right));
}

void update2D(int r, int lo, int hi, int P, int Q, ll k) {
    if (lo == hi) {
        ins(it[r].x, Q, k);
        return;
    }

    int mid = (lo + hi)/2;

    if (P <= mid) {
        if (it[r].left == -1) {
            it.emplace_back();
            it[r].left = it.size() - 1;
            it[it[r].left].x = nilt;
        }
        update2D(it[r].left, lo, mid, P, Q, k);
    }
    else {
        if (it[r].right == -1) {
            it.emplace_back();
            it[r].right = it.size() - 1;
            it[it[r].right].x = nilt;
        }
        update2D(it[r].right, mid + 1, hi, P, Q, k);
    }

    up(r, Q);
}

ll get(int r, int lo, int hi, int P, int Q, int U, int V) {
    if (hi < P || Q < lo || r == -1)
        return 0;

    if (P <= lo && hi <= Q) {
        if (it[r].x == nilt)
            return 0;
        tnode x, y, z;
        split(it[r].x, U - 1, x, y);
        split(y, V, y, z);

        ll ans = y->GCD;

        it[r].x = join(x, join(y, z));

        return ans;
    }

    int mid = (lo + hi)/2;

    return __gcd(get(it[r].left, lo, mid, P, Q, U, V), get(it[r].right, mid + 1, hi, P, Q, U, V));
}


void init(int _R, int _C) {
    nilt = new Node();
    it.emplace_back();
    it[0].x = nilt;

    R = _R;
    C = _C;
}

void update(int P, int Q, ll K) {
    update2D(0, 0, R - 1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return get(0, 0, R - 1, P, U, Q, V);
}

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