Submission #363870

#	Time	Username	Problem	Language	Result	Execution time	Memory
363870		Gareton	게임 (IOI13_game)	C++14	100 / 100	10341 ms	132368 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define orset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#pragma GCC optimize("O3")
// #pragma GCC target("sse", "sse2", "sse3", "sse4")
//#pragma GCC target("avx2")
#define int long long
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
#define all(a) (a.begin()), (a.end())
#define gsz(x) ((int)x.size())
#define endl "\n"
#define LOCAL
#ifdef LOCAL
#define dbg(x) cerr << #x << ":" << (x) << endl
#define print(x) cerr << (x) << endl
#else
#define dbg(x) 0
#define print(x) 0
#endif

using namespace std;
using namespace __gnu_pbds;

const int N = 2e6 + 10;
const int B = 340;
const ll inf = 1e18 + 10;
const ll mod = 1e9 + 7;

mt19937 rnd(4);//chrono::high_resolution_clock::now().time_since_epoch().count());

long long gcd2(long long X, long long Y) {
    assert(X >= 0 && Y >= 0);

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct nodey{
    int x, y, prior = rnd();
    int val, gcd;
    int l = -1, r = -1;
};

struct nodex{
    int l = -1, r = -1;
    int rooty = -1;
};

nodex tx[N];
nodey ty[N];
int n, m;
int topx = 0, topy = 0;
int rootx = -1;

int getgcd(int v)
{
    return v == -1 ? 0 : ty[v].gcd;
}

void updy(int v)
{
    if(v == -1) return;

    ty[v].gcd = gcd2(gcd2(ty[v].val, getgcd(ty[v].l)), getgcd(ty[v].r));
}



int mergey(int l, int r)
{
    if(l == -1) return r;
    if(r == -1) return l;

    if(ty[l].prior > ty[r].prior)
    {
        ty[l].r = mergey(ty[l].r, r);

        updy(l);

        return l;
    }
    else
    {
        ty[r].l = mergey(l, ty[r].l);

        updy(r);

        return r;
    }
}

pii splity(int v, pii k)
{
    if(v == -1) return {-1, -1};

    if(make_pair(ty[v].y, ty[v].x) > k)
    {
        pii p = splity(ty[v].l, k);

        ty[v].l = p.y;
        updy(v);

        return {p.x, v};
    }
    else
    {
        pii p = splity(ty[v].r, k);

        ty[v].r = p.x;
        updy(v);

        return {v, p.y};
    }
}

int createx()
{
    int v = topx++;

    return v;
}

map<pii, int> mp;

int gety(int &v, int ly, int ry)
{
    pii p1 = splity(v, {ly - 1, inf});
    pii p2 = splity(p1.y, {ry, inf});

    int val = getgcd(p2.x);

    v = mergey(p1.x, mergey(p2.x, p2.y));

    return val;
}

int getx(int tl, int tr, int v, int lx, int rx, int ly, int ry)
{
    if(v == -1)
        return 0;

    if(tl > rx || tr < lx)
        return 0;

    if(tl >= lx && tr <= rx)
        return gety(tx[v].rooty, ly, ry);

    int mid = (tl + tr) / 2;

    return gcd2(getx(tl, mid, tx[v].l, lx, rx, ly, ry), getx(mid + 1, tr, tx[v].r, lx, rx, ly, ry));
}

int createy(int x, int y, int val)
{
    int v = topy++;

    ty[v].x = x;
    ty[v].y = y;
    ty[v].val = ty[v].gcd = val;

    return v;
}

void changey(int &v, int x, int y, int val)
{
    pii p1 = splity(v, {y, x - 1});
    pii p2 = splity(p1.y, {y, x});

    v = mergey(p1.x, mergey(createy(x, y, val), p2.y));
}

int changex(int tl, int tr, int v, int x, int y, int val)
{
    if(tl > x || tr < x)
        return v;

    if(v == -1)
        v = createx();

    changey(tx[v].rooty, x, y, val);

    if(tl == tr)
        return v;

    int mid = (tl + tr) / 2;

    tx[v].l = changex(tl, mid, tx[v].l, x, y, val);
    tx[v].r = changex(mid + 1, tr, tx[v].r, x, y, val);

    return v; 
}

void init(int32_t n, int32_t m) 
{
    ::n = n;
    ::m = m;
}

void update(int32_t x, int32_t y, ll val) 
{
    rootx = changex(0, (ll)n - 1, rootx, x, y, val);
}

long long calculate(int32_t x1, int32_t y1, int32_t x2, int32_t y2) 
{
    return getx(0, (ll)n - 1, rootx, x1, x2, y1, y2);
}

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