Submission #945751

#	Time	Username	Problem	Language	Result	Execution time	Memory
945751		Der_Vlapos	Game (IOI13_game)	C++17	10 / 100	1875 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long

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 tree
{
    tree *l = NULL, *r = NULL;
    int lv, rv;
    ll res = 0;

    tree(int lv, int rv) : lv(lv), rv(rv) {}

    void enlarge()
    {
        int m = (lv + rv) >> 1;
        if (l == NULL)
            l = new tree(lv, m);
        if (r == NULL)
            r = new tree(m, rv);
    }

    ll get(int L, int R)
    {
        enlarge();
        if (L <= lv and rv <= R)
        {
            return res;
        }
        if (rv <= L or R <= lv)
            return 0;
        assert(rv - lv > 0);
        return gcd2(l->get(L, R), r->get(L, R));
    }

    void set(int pos, ll val)
    {
        enlarge();
        if (rv - lv == 1)
        {
            res = val;
            return;
        }
        assert(rv - lv > 0);
        int m = (lv + rv) >> 1;
        if (pos < m)
            l->set(pos, val);
        else
            r->set(pos, val);
        res = gcd2(l->res, r->res);
    }
};

struct TREE
{
    TREE *l = NULL, *r = NULL;
    int lv, rv, maxY;
    tree *res;

    TREE(int lv, int rv, int maxY) : lv(lv), rv(rv), maxY(maxY) { res = new tree(0, maxY); }

    void enlarge()
    {
        int m = (lv + rv) >> 1;
        if (l == NULL)
            l = new TREE(lv, m, maxY);
        if (r == NULL)
            r = new TREE(m, rv, maxY);
    }

    ll get(int L, int R, int lx, int ly)
    {
        enlarge();
        if (L <= lv and rv <= R)
        {
            return res->get(lx, ly);
        }
        if (rv <= L or R <= lv)
            return 0;
        return gcd2(l->get(L, R, lx, ly), r->get(L, R, lx, ly));
    }

    void set(int x, int y, ll val)
    {
        enlarge();
        if (rv - lv == 1)
        {
            res->set(y, val);
            return;
        }
        int m = (lv + rv) >> 1;
        if (x < m)
            l->set(x, y, val);
        else
            r->set(x, y, val);
        res->set(y, gcd2(l->res->get(y, y + 1), r->res->get(y, y + 1)));
    }
};

TREE help(0, 1e9 + 10, 1e9 + 10);

void init(int R, int C)
{
    /* ... */
}

void update(int P, int Q, long long K)
{
    /* ... */
    help.set(P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    /* ... */
    return help.get(min(P, U), max(P, U) + 1, min(Q, V), max(Q, V) + 1);
}

// /////////////////////

// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include <vector>
// #include "game.h"

// #define MAX_SIZE 1000000000
// #define MAX_N 272000

// int main()
// {
//     int R, C, N;
//     int P, Q, U, V;
//     long long K;
//     int i, type;

//     assert(scanf("%d", &R) == 1);
//     assert(scanf("%d", &C) == 1);
//     assert(scanf("%d", &N) == 1);

//     init(R, C);
//     std::vector<long long> answers;

//     for (i = 0; i < N; i++)
//     {
//         assert(scanf("%d", &type) == 1);
//         if (type == 1)
//         {
//             assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
//             update(P, Q, K);
//         }
//         else if (type == 2)
//         {
//             assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
//             answers.push_back(calculate(P, Q, U, V));
//         }
//     }
//     for (auto answer : answers)
//     {
//         printf("%lld\n", answer);
//     }

//     return 0;
// }

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