Submission #384014

#	Time	Username	Problem	Language	Result	Execution time	Memory
384014		ParsaAlizadeh	Game (IOI13_game)	C++17	10 / 100	13086 ms	9724 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr int N = 3e6;

ll gcd2(ll x, ll y) {
    ll tmp;
    while (x != y && y != 0) {
        tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}

ll tr[N];
int root, ul[N], ur[N], dl[N], dr[N];
pii A[N], B[N];

int new_node(const pii & _A, const pii & _B) {
    static int timer = 1;
    A[timer] = _A;
    B[timer] = _B;
    assert(timer < N);
    return timer++;
}

void push(int id, int x, int y, ll val) {
    if (x < A[id].X || y < A[id].Y || x >= B[id].X || y >= B[id].Y)
        return;
    if (A[id].X + 1 == B[id].X) {
        assert(A[id].Y + 1 == B[id].Y);
        tr[id] = val;
        return;
    }
    if (!ul[id]) {
        pii mid = {(A[id].X + B[id].X) >> 1, (A[id].Y + B[id].Y) >> 1};
        ul[id] = new_node({A[id].X, A[id].Y}, {mid.X, mid.Y});
        ur[id] = new_node({A[id].X, mid.Y}, {mid.X, B[id].Y});
        dl[id] = new_node({mid.X, A[id].Y}, {B[id].X, mid.Y});
        dr[id] = new_node({mid.X, mid.Y}, {B[id].X, B[id].Y});
    }        
    tr[id] = 0;
    push(ul[id], x, y, val); tr[id] = gcd2(tr[id], tr[ul[id]]);
    push(ur[id], x, y, val); tr[id] = gcd2(tr[id], tr[ur[id]]);
    push(dl[id], x, y, val); tr[id] = gcd2(tr[id], tr[dl[id]]);
    push(dr[id], x, y, val); tr[id] = gcd2(tr[id], tr[dr[id]]);
}

ll query(int id, const pii & C, const pii & D) {
    if (tr[id] == 0)
        return 0;
    if (D.X <= A[id].X || D.Y <= A[id].Y || B[id].X <= C.X || B[id].Y <= C.Y)
        return 0;
    if (C.X <= A[id].X && C.Y <= A[id].Y && B[id].X <= D.X && B[id].Y <= D.Y)
        return tr[id];
    ll res = 0;
    res = gcd2(res, query(ul[id], C, D));
    res = gcd2(res, query(ur[id], C, D));
    res = gcd2(res, query(dl[id], C, D));
    res = gcd2(res, query(dr[id], C, D));
    return res;
}

/*
struct Tree {
    ll data;
    pii A, B;
    Tree *ul, *ur, *dl, *dr;

    Tree(const pii & _A, const pii & _B) : data(0), A(_A), B(_B) {}

    void push(int x, int y, ll val) {
        if (x < A.X || y < A.Y || x >= B.X || y >= B.Y)
            return;
        if (A.X + 1 == B.X) {
            assert(A.Y + 1 == B.Y);
            data = val;
            return;
        }
        if (ul == nullptr) {
            pii mid = {(A.X + B.X) >> 1, (A.Y + B.Y) >> 1};
            ul = new Tree({A.X, A.Y}, {mid.X, mid.Y});
            ur = new Tree({A.X, mid.Y}, {mid.X, B.Y});
            dl = new Tree({mid.X, A.Y}, {B.X, mid.Y});
            dr = new Tree({mid.X, mid.Y}, {B.X, B.Y});
        }            
        data = 0;
        ul->push(x, y, val); data = gcd2(data, ul->data);
        ur->push(x, y, val); data = gcd2(data, ur->data);
        dl->push(x, y, val); data = gcd2(data, dl->data);
        dr->push(x, y, val); data = gcd2(data, dr->data);
    }

    ll query(const pii & C, const pii & D) {
        if (data == 0)
            return 0; // this implies ul != nullptr
        if (D.X <= A.X || D.Y <= A.Y || B.X <= C.X || B.Y <= C.Y)
            return 0;
        if (C.X <= A.X && C.Y <= A.Y && B.X <= D.X && B.Y <= D.Y)
            return data;
        ll r1 = gcd2(ul->query(C, D), ur->query(C, D)),
           r2 = gcd2(dl->query(C, D), dr->query(C, D));
        return gcd2(r1, r2);
    }
} *root;
*/

void init(int R, int C) {
    int n = 1;
    while (n < R || n < C) {
        n <<= 1;
    }
    root = new_node({0, 0}, {n, n});
}

void update(int P, int Q, ll K) {
    push(root, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query(root, {P, Q}, {U + 1, V + 1});
}

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