Submission #412535

#	Time	Username	Problem	Language	Result	Execution time	Memory
412535		albertolg101	Game (IOI13_game)	C++17	0 / 100	1 ms	292 KiB

game

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

using namespace std;

const int MXN = 1e9;

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 node2
{
    int x, xend;
    node2 *l, *r;
    long long val;

    node2(int low, int high): x(low), xend(high), l(nullptr), r(nullptr), val(0LL){}
};

struct node1
{
    node1 *l, *r;
    node2 *z;

    node1(): l(nullptr), r(nullptr)
    {
        z = new node2(1, MXN);
    }
};

void update2 (node2 *t, int pos, int val)
{
    int x = t->x,
        xend = t->xend,
        mid = (x + xend) / 2;

    if(x == xend)
    {
        t->val = val;
        return ;
    }

    node2 *&t2 = pos <= mid ? t->l : t->r ; 

    if(t2 == nullptr)
    {
        t2 = new node2(pos, pos);
        t2->val = val;
    }

    else if(t2->x <= pos and pos <= t2->xend)
    {
        update2(t2, pos, val);
    }

    else
    {
        do
        {
            (pos <= mid ? xend : x) = mid + (pos > mid);
            mid = (x + xend) / 2;
        } while((pos <= mid) == (t2->x <= mid));

        node2 *t3 = new node2(x, xend);
        (t2->x <= mid ? t3->l : t3->r) = t2;
        t2 = t3;

        update2(t3, pos, val);
    }

    t->val = gcd2((t->l ? t->l->val : 0LL),
                  (t->r ? t->r->val : 0LL));
}

long long query2 (node2 *t, int l, int r)
{
    if(t == nullptr or t->x > r or t->xend < l)
        return 0LL;

    if(l <= t->x and t->xend <= r)
    {
        return t->val;
    }

    return gcd2(query2(t->l, l, r), 
                query2(t->r, l, r));
}

void update1 (node1 *t, int x, int xend, int pos1, int pos2, int val)
{
    if(x == xend)
    {
        update2(t->z, pos2, val);
        return ;
    }

    int mid = (x + xend) / 2;
    node1 *&t2 = (pos1 <= mid ? t->l : t->r);
    (pos1 <= mid ? xend : x) = mid + (pos1 > mid);

    if(t2 == nullptr)
        t2 = new node1();

    update1(t2, x, xend, pos1, pos2, val);

    val = gcd2(t->l ? query2(t->l->z, pos2, pos2) : 0LL,
               t->r ? query2(t->r->z, pos2, pos2) : 0LL);

    update2(t->z, pos2, val);
}

long long query1 (node1 *t, int x, int xend, int l1, int r1, int l2, int r2)
{
    if(t == nullptr or x > r1 or xend < l1)
        return 0LL;

    if(l1 <= x and xend <= r1)
    {
        return query2(t->z, l2, r2);
    }

    int mid = (x + xend) / 2;

    return gcd2(query1(t->l, x, mid, l1, r1, l2, r2), 
                query1(t->r, mid+1, xend, l1, r1, l2, r2));
}

node1 *root = new node1();

void init(int R, int C) {

}

void update(int P, int Q, long long K) {
    update1(root, 1, MXN, P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query1(root, 1, MXN, P+1, U+1, Q+1, V+1);
}

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