제출 #1125970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125970		rm13	게임 (IOI13_game)	C++20	100 / 100	8669 ms	77856 KiB

game

#include "game.h"
// #if DEBUG
#pragma GCC optimize("Ofast,fast-math,unroll-loops,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #endif

#include <assert.h>
#include <string.h>
#include <time.h>

#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
using namespace std::chrono;

#define SZ(x) ((int)x.size())
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define clrall(name, val) memset(name, (val), sizeof(name))
#define eraseDuplicate(v) v.resize(distance(v.begin(), unique(all(v))))
#define EPS 1e-9
#define ll long long
#define ull long long unsigned
#define SF scanf
#define PF printf
#define sf scanf
#define pf printf
#define psb(b) push_back((b))
#define ppb() pop_back()
#define oo (1 << 28)
#define inf 0x3f3f3f3f
#define mp make_pair
#define mt make_tuple
#define get(a, b) get<b>(a)
#define fs first
#define sc second
#define Read freopen("sample.in", "r", stdin)
#define Write freopen("sample-me.out", "w", stdout)
#define __ std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl "\n"
#define casePrint(cas) cout << "Case " << cas << ": "
#define casePrintNL(cas) cout << "Case " << cas << ":\n"

template <class T>
inline T _lcm(T a, T b)
{
    T g = _gcd(a, b);
    return ((a / g) * b);
}
template <class T1>
void deb(T1 e1)
{
    cerr << e1 << "\n";
}
template <class T1, class T2>
void deb(T1 e1, T2 e2)
{
    cerr << e1 << " " << e2 << "\n";
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3)
{
    cerr << e1 << " " << e2 << " " << e3 << "\n";
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4)
{
    cerr << e1 << " " << e2 << " " << e3 << " " << e4 << "\n";
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5)
{
    cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << "\n";
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6)
{
    cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
         << "\n";
}
template <class T1, class T2, class T3, class T4, class T5, class T6, class T7>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6, T7 e7)
{
    cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
         << " " << e7 << "\n";
}

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

mt19937 rng((unsigned int)steady_clock::now().time_since_epoch().count());
struct Treap
{
private:
    int key;
    ll data, gcdVal;
    unsigned int priority;
    Treap *leftKid, *rightKid;

    static void recalculate(Treap *node)
    {
        if (!node)
            return;
        node->gcdVal = gcd2(gcd2(node->data, getGcdVal(node->leftKid)), getGcdVal(node->rightKid));
    }

    static ll getGcdVal(Treap *node) { return node ? node->gcdVal : 0; }

    static void print(Treap *node, bool &isFirst, bool isDebug)
    {
        if (!node)
            return;
        print(node->leftKid, isFirst, isDebug);
        if (!isFirst)
        {
            if (isDebug)
                cerr << " ";
            else
                cout << " ";
        }
        if (isDebug)
            cerr << "(" << node->key << "," << node->data << ")";
        else
            cout << node->data;
        isFirst = false;
        print(node->rightKid, isFirst, isDebug);
        return;
    }

public:
    Treap() : key(-1), data(0), gcdVal(0), priority(rng()), leftKid(nullptr), rightKid(nullptr) {}
    Treap(int key, ll data) : key(key), data(data), gcdVal(data), priority(rng()), leftKid(nullptr), rightKid(nullptr) {}

    static Treap *merge(Treap *l, Treap *r)
    {
        if (!l)
            return r;
        if (!r)
            return l;
        if (l->priority < r->priority)
        {
            l->rightKid = merge(l->rightKid, r);
            recalculate(l);
            return l;
        }
        else
        {
            r->leftKid = merge(l, r->leftKid);
            recalculate(r);
            return r;
        }
    }

    static pair<Treap *, Treap *> split(Treap *node, int key)
    {
        if (!node)
            return {nullptr, nullptr};
        if (node->key <= key)
        {
            auto rightRes = split(node->rightKid, key);
            node->rightKid = rightRes.first;
            recalculate(node);
            return {node, rightRes.second};
        }
        else
        {
            auto leftRes = split(node->leftKid, key);
            node->leftKid = leftRes.second;
            recalculate(node);
            return {leftRes.first, node};
        }
    }

    static void debug(Treap *node)
    {
        if (!node)
        {
            deb("nullptr", node);
            return;
        }
        deb("in debug", node, node->key, node->data, node->priority);
    }

    static Treap *insert(Treap *node, int pos, ll val)
    {
        if (!node)
            return new Treap(pos, val);
        pair<Treap *, Treap *> firstSplit = split(node, pos - 1);
        pair<Treap *, Treap *> secondSplit = split(firstSplit.second, pos);
        return merge(firstSplit.first, merge(new Treap(pos, val), secondSplit.second));
    }

    static ll rangeGcd(Treap *node, int l, int r)
    {
        if (l > r)
            return 0;
        pair<Treap *, Treap *> firstSplit = split(node, r);
        pair<Treap *, Treap *> secondSplit = split(firstSplit.first, l - 1);
        ll res = getGcdVal(secondSplit.second);
        node = merge(merge(secondSplit.first, secondSplit.second), firstSplit.second);
        return res;
    }

    static void print(Treap *node, bool isDebug = false)
    {
        bool isFirst = true;
        print(node, isFirst, isDebug);
        if (isDebug)
            cerr << endl;
        else
            cout << endl;
        return;
    }
};

class TreapSegTree
{
public:
    Treap *treap;
    TreapSegTree *left, *right;
    int N;

    TreapSegTree() : N(0), treap(nullptr), left(nullptr), right(nullptr) {}
    TreapSegTree(int n) : N(n), treap(nullptr), left(nullptr), right(nullptr) {}

private:
    static TreapSegTree *update(TreapSegTree *node, int start, int end, int x, int y, ll value)
    {
        if (!node)
            node = new TreapSegTree();

        if (x < start || x > end)
            return node;

        auto pushUp = [&]() -> void
        {
            ll updatedVal = 0;
            if (node->left)
                updatedVal = gcd2(updatedVal, Treap::rangeGcd(node->left->treap, y, y));
            if (node->right)
                updatedVal = gcd2(updatedVal, Treap::rangeGcd(node->right->treap, y, y));
            node->treap = Treap::insert(node->treap, y, updatedVal);
        };
        if (start == end)
        {
            node->treap = Treap::insert(node->treap, y, value);
        }
        else
        {
            int mid = (start + end) / 2;
            node->left = update(node->left, start, mid, x, y, value);
            node->right = update(node->right, mid + 1, end, x, y, value);
            pushUp();
        }

        return node;
    }

    static ll query(TreapSegTree *node, int start, int end, int l, int r, int q_start, int q_end)
    {
        if (!node || r < start || end < l)
            return 0;

        if (l <= start && end <= r)
        {
            return Treap::rangeGcd(node->treap, q_start, q_end);
        }

        int mid = (start + end) / 2;
        ll leftGcdVal = query(node->left, start, mid, l, r, q_start, q_end);
        ll rightGcdVal = query(node->right, mid + 1, end, l, r, q_start, q_end);
        return gcd2(leftGcdVal, rightGcdVal);
    }

public:
    static TreapSegTree *pointUpdate(TreapSegTree *root, int x, int y, ll value)
    {
        if (!root)
            return root;
        return update(root, 1, root->N, x, y, value);
    }

    static ll rangeQuery(TreapSegTree *root, int x1, int y1, int x2, int y2)
    {
        if (!root)
            return 0;
        return query(root, 1, root->N, x1, x2, y1, y2);
    }
};

TreapSegTree *sTree;

void init(int R, int C)
{
    sTree = new TreapSegTree(R);
}

void update(int P, int Q, long long K)
{
    P++;
    Q++;
    sTree = TreapSegTree::pointUpdate(sTree, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    P++;
    Q++;
    U++;
    V++;
    return TreapSegTree::rangeQuery(sTree, P, Q, U, V);
}

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