Submission #1246791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246791		Amadoo	게임 (IOI13_game)	C++20	36 / 100	13084 ms	9360 KiB

game

#include "game.h"
#include <bits/stdc++.h>
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;
}

const long long MAX = 1e18;

using T = long long;
inline T merge(const T &a, const T &b) { return gcd2(a, b); }
const T default_val = 0;

struct NodeY {
    int y;
    T val;
    T sum;
    int pr;
    NodeY *l = nullptr, *r = nullptr;
    NodeY(int _y, const T &_v): y(_y), val(_v), sum(_v), pr(rand()) {}
};

inline T sumY(NodeY *t) { return t ? t->sum : default_val; }
inline void pullY(NodeY *t) {
    if(t) t->sum = merge(merge(sumY(t->l), t->val), sumY(t->r));
}
NodeY* rotateYRight(NodeY *t) {
    NodeY *p = t->l;
    t->l = p->r; p->r = t;
    pullY(t); pullY(p);
    return p;
}
NodeY* rotateYLeft(NodeY *t) {
    NodeY *p = t->r;
    t->r = p->l; p->l = t;
    pullY(t); pullY(p);
    return p;
}
NodeY* insertY(NodeY *t, int y, const T &v) {
    if(!t) return new NodeY(y, v);
    if(t->y == y) t->val = v;
    else if(y < t->y) {
        t->l = insertY(t->l, y, v);
        if(t->l->pr > t->pr) t = rotateYRight(t);
    } 
    else {
        t->r = insertY(t->r, y, v);
        if(t->r->pr > t->pr) t = rotateYLeft(t);
    }
    pullY(t);
    return t;
}
T queryY(NodeY *t, int y1, int y2) {
    if(!t) return default_val;
    if(t->y < y1) return queryY(t->r, y1, y2);
    if(t->y > y2) return queryY(t->l, y1, y2);
    return merge(merge(queryY(t->l, y1, y2), t->val), queryY(t->r, y1, y2));
}

struct NodeX {
    int x;
    NodeX *l = nullptr, *r = nullptr;
    NodeY *yt = nullptr;
    NodeX() {}
};

struct ImplicitSegTree2D {
    int x_min, x_max;
    NodeX *root = nullptr;
    ImplicitSegTree2D(): x_min(0), x_max(0), root(nullptr) {}
    void updateX(NodeX *&t, int lx, int rx, int x, int y, const T &v) {
        if(!t) t = new NodeX();
        if(lx == rx) {
            t->yt = insertY(t->yt, y, v);
            return;
        }
        int mid = lx + ((rx - lx) >> 1);
        if(x <= mid) updateX(t->l, lx, mid, x, y, v);
        else updateX(t->r, mid+1, rx, x, y, v);
        T L = t->l ? queryY(t->l->yt, y, y) : default_val;
        T R = t->r ? queryY(t->r->yt, y, y) : default_val;
        t->yt = insertY(t->yt, y, merge(L, R));
    }
    void update(int x, int y, const T &v) {
        if(x < x_min || x > x_max) return;
        updateX(root, x_min, x_max, x, y, v);
    }
    T queryX(NodeX *t, int lx, int rx, int x1, int x2, int y1, int y2) const {
        if(!t || x2 < lx || rx < x1) return default_val;
        if(x1 <= lx && rx <= x2) return queryY(t->yt, y1, y2);
        int mid = lx + ((rx - lx) >> 1);
        return merge(queryX(t->l, lx, mid, x1, x2, y1, y2), queryX(t->r, mid+1, rx, x1, x2, y1, y2));
    }
    T query(int x1, int y1, int x2, int y2) const {
        if(x2 < x_min || x_max < x1) return default_val;
        x1 = max(x1, x_min); x2 = min(x2, x_max);
        return queryX(root, x_min, x_max, x1, x2, y1, y2);
    }
};

ImplicitSegTree2D st;

void init(int R, int C) {
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    st.x_min = 0;
    st.x_max = R - 1;
}

void update(int P, int Q, long long K) {
    st.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st.query(P, Q, U, V);
}

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