제출 #396509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396509		phathnv	게임 (IOI13_game)	C++11	63 / 100	2496 ms	256004 KiB

game

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

typedef long long ll;

using namespace std;

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 Node{
    int l, r;
    ll data;
    Node *Left, *Right;
    Node(int _l, int _r){
        l = _l;
        r = _r;
        data = 0;
        Left = Right = nullptr;
    }
    ll get(int u, int v){
        if (v < l || r < u || data == 0)
            return 0;
        if (u <= l && r <= v)
            return data;
        ll res = 0;
        if (Left != nullptr)
            res = gcd2(res, Left->get(u, v));
        if (Right != nullptr)
            res = gcd2(res, Right->get(u, v));
        return res;
    }
    void update(int pos, ll val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            data = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid){
            if (Left == nullptr)
                Left = new Node(l, mid);
            Left->update(pos, val);
        } else {
            if (Right == nullptr)
                Right = new Node(mid + 1, r);
            Right->update(pos, val);
        }
        data = 0;
        if (Left != nullptr)
            data = gcd2(data, Left->data);
        if (Right != nullptr)
            data = gcd2(data, Right->data);
    }
};

struct Node2{
    int l, r;
    Node *data;
    Node2 *Left, *Right;
    Node2(int _l, int _r){
        l = _l;
        r = _r;
        data = new Node(0, 1e9);
        Left = Right = nullptr;
    }
    ll get(int x, int y, int u, int v){
        if (y < l || r < x || data->data == 0)
            return 0;
        if (x <= l && r <= y)
            return data->get(u, v);
        ll res = 0;
        if (Left != nullptr)
            res = gcd2(res, Left->get(x, y, u, v));
        if (Right != nullptr)
            res = gcd2(res, Right->get(x, y, u, v));
        return res;
    }
    void update(int x, int y, ll val){
        if (x < l || r < x)
            return;
        if (l == r){
            data->update(y, val);
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid){
            if (Left == nullptr)
                Left = new Node2(l, mid);
            Left->update(x, y, val);
        } else {
            if (Right == nullptr)
                Right = new Node2(mid + 1, r);
            Right->update(x, y, val);
        }
        ll newVal = 0;
        if (Left != nullptr)
            newVal = gcd2(newVal, Left->data->get(y, y));
        if (Right != nullptr)
            newVal = gcd2(newVal, Right->data->get(y, y));
        data->update(y, newVal);
    }
};

Node2 *st;

void init(int r, int c) {
    st = new Node2(0, 1e9);
}

void update(int p, int q, long long k) {
    st->update(p, q, k);
}

long long calculate(int x, int y, int u, int v) {
    assert(x <= u && y <= v);
    return st->get(x, u, y, v);
}

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