제출 #1199771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199771		Hamed_Ghaffari	게임 (IOI13_game)	C++20	100 / 100	4582 ms	57184 KiB

game

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using ull = unsigned long long;

#define mid ((l+r)>>1)

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

int R, C;

struct treap {
    treap *lc, *rc;
    ull pri;
    int pos;
    ll val, ans;
    treap(int pos, ll val):
    lc(NULL), rc(NULL), pri(rng()), pos(pos), val(val), ans(val) {}
    inline void pull() {
        ans = 0;
        if(lc) ans = __gcd(ans, lc->ans);
        if(rc) ans = __gcd(ans, rc->ans);
        ans = __gcd(ans, val);
    }
};

treap *merge(treap *u, treap *v) {
    if(!u) return v;
    if(!v) return u;
    if(u->pri>v->pri) {
        u->rc = merge(u->rc, v);
        return u->pull(), u;
    }
    v->lc = merge(u, v->lc);
    return v->pull(), v;
}

void split(treap *v, int x, treap *&l, treap *&r) {
    if(!v) { l=NULL; r=NULL; return; }
    if(v->pos<=x) {
        split(v->rc, x, v->rc, r);
        (l=v)->pull();
    }
    else {
        split(v->lc, x, l, v->lc);
        (r=v)->pull();
    }
}

void upd(treap *&v, int p, ll x) {
    treap *A, *B, *C;
    split(v, p-1, A, B);
    split(B, p, B, C);
    if(B) B->val = B->ans = x;
    else B = new treap(p, x);
    v = merge(merge(A, B), C);
}

ll get(treap *&v, int s, int e) {
    treap *A, *B, *C;
    split(v, s-1, A, B);
    split(B, e-1, B, C);
    ll ans = B ? B->ans : 0;
    v = merge(merge(A, B), C);
    return ans;
}

struct seg {
    seg *lc, *rc;
    treap *ds;
    seg(): lc(NULL), rc(NULL), ds(NULL) {}
};

ll upd2(int p, int q, ll x, seg *v, int l=0, int r=R) {
    if(r-l == 1) {
        upd(v->ds, q, x);
        return x;
    }
    ll val=0;
    if(p<mid) {
        if(!v->lc) v->lc = new seg();
        val = __gcd(upd2(p, q, x, v->lc, l, mid), v->rc ? get(v->rc->ds, q, q+1) : 0);
    }
    else {
        if(!v->rc) v->rc = new seg();
        val = __gcd(v->lc ? get(v->lc->ds, q, q+1) : 0, upd2(p, q, x, v->rc, mid, r));
    }
    upd(v->ds, q, val);
    return val;
}

ll get2(int s1, int e1, int s2, int e2, seg *v, int l=0, int r=R) {
    if(s1>=r || l>=e1 || !v) return 0;
    if(s1<=l && r<=e1) return get(v->ds, s2, e2);
    return __gcd(
        get2(s1, e1, s2, e2, v->lc, l, mid),
        get2(s1, e1, s2, e2, v->rc, mid, r)
    );
}

seg *ds;

void init(int R, int C) {
    ::R = R;
    ::C = C;
    ds = new seg();
}
void update(int P, int Q, long long K) {
    upd2(P, Q, K, ds);
}
long long calculate(int P, int Q, int U, int V) {
    return get2(P, U+1, Q, V+1, ds);
}

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