Submission #1090440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090440		vjudge1	Game (IOI13_game)	C++14	10 / 100	13090 ms	16328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y)
{
    if (!X)
        return Y;
    ll an = __builtin_ctzll(X | Y);
    X >>= __builtin_ctzll(X);
    Y >>= __builtin_ctzll(Y);
    while (Y)
    {
        if (X > Y)
            swap(X, Y);
        Y -= X;
        Y >>= __builtin_ctzll(Y);
    }
    return X << an;
}
ll T = 1;
vector<ll> sg = {0};
vector<int> pa = {0}, cl = {-1}, cr = {-1}, wl = {0}, wr = {0}, wt = {0}, wb = {0};
void cre(int i, int x)
{
    sg.push_back(0);
    pa.push_back(i);
    cl.push_back(-1);
    cr.push_back(-1);
    if (wr[i] - wl[i] > wb[i] - wt[i])
    {
        ll md = ((wl[i] + wr[i]) >> 1);
        wt.push_back(wt[i]);
        wb.push_back(wb[i]);
        if (x)
        {
            wl.push_back(md);
            wr.push_back(wr[i]);
        }
        else
        {
            wl.push_back(wl[i]);
            wr.push_back(md);
        }
    }
    else
    {
        ll md = ((wt[i] + wb[i]) >> 1);
        wl.push_back(wl[i]);
        wr.push_back(wr[i]);
        if (x)
        {
            wt.push_back(md);
            wb.push_back(wb[i]);
        }
        else
        {
            wt.push_back(wt[i]);
            wb.push_back(md);
        }
    }
    if (x)
        cr[i] = T;
    else
        cl[i] = T;
    T++;
}
int l, r, t, b;
ll x;
void upd(int i)
{
    if (wt[i] > l || wb[i] <= l || wl[i] > r || wr[i] <= r)
        return;
    if (wt[i] == l && wb[i] == l + 1 && wl[i] == r && wr[i] == r + 1)
    {
        sg[i] = x;
        return;
    }
    if (cl[i] == -1)
        cre(i, 0);
    upd(cl[i]);
    if (cr[i] == -1)
        cre(i, 1);
    upd(cr[i]);
    sg[i] = gcd2(sg[cl[i]], sg[cr[i]]);
}
ll qu(int i)
{
    if (wt[i] >= b || wb[i] <= t || wl[i] >= r || wr[i] <= l)
        return 0;
    if (wt[i] >= t && wb[i] <= b && wl[i] >= l && wr[i] <= r)
        return sg[i];
    ll an = 0;
    if (cl[i] != -1)
        an = gcd2(qu(cl[i]), an);
    if (cr[i] != -1)
        an = gcd2(qu(cr[i]), an);
    return an;
}
void init(int R, int C)
{
    wr[0] = C;
    wb[0] = R;
}
void update(int P, int Q, ll K)
{
    l = P;
    r = Q;
    x = K;
    upd(0);
}
ll calculate(int P, int Q, int U, int V)
{
    t = P;
    b = U + 1;
    l = Q;
    r = V + 1;
    return qu(0);
}

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