제출 #423038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423038		wiwiho	게임 (IOI13_game)	C++14	10 / 100	13101 ms	12992 KiB

game

#include "game.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct Node1D{
    ll v = 0;
    int tag = -1;
    Node1D *l = nullptr, *r = nullptr;
};

struct Node2D{
    Node1D *rt = nullptr;
    Node2D *l = nullptr, *r = nullptr;
};

int n, m;
Node2D *rt = nullptr;

void pull1D(Node1D *node){
    node->v = __gcd(node->l == nullptr ? 0 : node->l->v, node->r == nullptr ? 0 : node->r->v);
}

Node1D *modify1D(int pos, ll v, int L, int R, Node1D *node){
    if(node == nullptr){
        node = new Node1D();
        node->v = v;
        node->tag = pos;
        return node;
    }
    if(pos == node->tag){
        node->v = v;
        return node;
    }
    assert(L != R);
    int M = (L + R) / 2;
    if(node->tag != -1){
        assert(node->l == nullptr && node->r == nullptr);
        if(node->tag <= M) node->l = modify1D(node->tag, node->v, L, M, node->l);
        else node->r = modify1D(node->tag, node->v, M + 1, R, node->r);
        node->tag = -1;
        node->v = 0;
    }
    if(pos <= M) node->l = modify1D(pos, v, L, M, node->l);
    else node->r = modify1D(pos, v, M + 1, R, node->r);
    pull1D(node);
    return node;
}

ll query1D(int l, int r, int L, int R, Node1D *node){
    if(node == nullptr) return 0;
    if(l <= node->tag && node->tag <= r) return node->v;
    assert(L != R);
    int M = (L + R) / 2;
    if(r <= M) return query1D(l, r, L, M, node->l);
    else if(l > M) return query1D(l, r, M + 1, R, node->r);
    else return __gcd(query1D(l, M, L, M, node->l), query1D(M + 1, r, M + 1, R, node->r));
}

void pull2D(Node2D *node, int y){
    ll lv = node->l == nullptr ? 0 : query1D(y, y, 0, m - 1, node->l->rt);
    ll rv = node->r == nullptr ? 0 : query1D(y, y, 0, m - 1, node->r->rt);
    node->rt = modify1D(y, __gcd(lv, rv), 0, m - 1, node->rt);
}

Node2D *modify2D(int x, int y, ll v, int L, int R, Node2D *node){
    if(node == nullptr) node = new Node2D();
    if(L == R){
        node->rt = modify1D(y, v, 0, m - 1, node->rt);
        return node;
    }
    int M = (L + R) / 2;
    if(x <= M) node->l = modify2D(x, y, v, L, M, node->l);
    else node->r = modify2D(x, y, v, M + 1, R, node->r);
    pull2D(node, y);
    return node;
}

ll query2D(int xl, int xr, int yl, int yr, int L, int R, Node2D *node){
    if(node == nullptr) return 0;
    if(xl == L && xr == R){
        return query1D(yl, yr, 0, m - 1, node->rt);
    }
    int M = (L + R) / 2;
    if(xr <= M) return query2D(xl, xr, yl, yr, L, M, node->l);
    else if(xl > M) return query2D(xl, xr, yl, yr, M + 1, R, node->r);
    else return __gcd(query2D(xl, M, yl, yr, L, M, node->l), query2D(M + 1, xr, yl, yr, M + 1, R, node->r));
}

void init(int R, int C){
    n = R; m = C;
}

void update(int P, int Q, long long K){
    rt = modify2D(P, Q, K, 0, n - 1, rt);
}

ll calculate(int P, int Q, int U, int V){
    return query2D(P, U, Q, V, 0, n - 1, rt);
}

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