Submission #1219269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219269		HappyCapybara	게임 (IOI13_game)	C++20	100 / 100	3182 ms	74312 KiB

game

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

#define ll long long

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 {
    node *lc, *rc;
    int pos, key, tl, tr;
    ll val, g;

    node(int p, ll v){
        lc = nullptr;
        rc = nullptr;
        tl = tr = pos = p;
        key = rand();
        val = g = v;
    }

    void update(){
        g = val;
        tl = tr = pos;
        if (lc){
            g = gcd(g, lc->g);
            tl = lc->tl;
        }
        if (rc){
            g = gcd(g, rc->g);
            tr = rc->tr;
        }
    }
};

struct treap {
    node* root;

    treap(){
        srand(rand());
        root = nullptr;
    }

    void split(node* t, int pos, node*& l, node*& r){
        if (!t){
            l = r = nullptr;
            return;
        }
        if (t->pos < pos){
            split(t->rc, pos, l, r);
            t->rc = l;
            l = t;
        }
        else {
            split(t->lc, pos, l, r);
            t->lc = r;
            r = t;
        }
        t->update();
    }

    node* merge(node* l, node* r){
        if (!l) return r;
        if (!r) return l;
        if (l->key < r->key){
            l->rc = merge(l->rc, r);
            l->update();
            return l;
        }
        else {
            r->lc = merge(l, r->lc);
            r->update();
            return r;
        }
    }

    bool find(int pos){
        node* t = root;
        while (t){
            if (t->pos == pos) return true;
            if (t->pos > pos) t = t->lc;
            else t = t->rc;
        }
        return false;
    }

    void update(node* t, int pos, ll val){
        if (t->pos == pos){
            t->val = val;
            t->update();
            return;
        }
        if (t->pos > pos) update(t->lc, pos, val);
        else update(t->rc, pos, val);
        t->update();
    }

    void insert(int pos, ll val){
        if (find(pos)) update(root, pos, val);
        else {
            node *l, *r;
            split(root, pos, l, r);
            root = merge(l, merge(new node(pos, val), r));
        }
    }

    ll query(node* t, int lb, int rb){
        if (t->tr < lb || rb < t->tl) return 0;
        if (lb <= t->tl && t->tr <= rb) return t->g;
        ll ans = 0;
        if (lb <= t->pos && t->pos <= rb) ans = t->val;
        if (t->lc) ans = gcd2(ans, query(t->lc, lb, rb));
        if (t->rc) ans = gcd2(ans, query(t->rc, lb, rb));
        return ans;
    }
    ll query(int lb, int rb){
        if (root) return query(root, lb, rb);
        return 0;
    }
};

struct st {
    st *lc, *rc;
    treap *t;
    int tl, tr;
    
    st(int lb, int rb){
        lc = rc = nullptr;
        tl = lb;
        tr = rb;
        t = new treap();
    }

    void fix(int pos){
        ll val = 0;
        if (lc) val = gcd(val, lc->t->query(pos, pos));
        if (rc) val = gcd(val, rc->t->query(pos, pos));
        t->insert(pos, val);
    }

    void update(int x, int y, ll val){
        if (x < tl || tr < x) return;
        if (tl == tr){
            t->insert(y, val);
            return;
        }
        int tm = (tl+tr)/2;
        if (x <= tm){
            if (!lc) lc = new st(tl, tm);
            lc->update(x, y, val);
        }
        else {
            if (!rc) rc = new st(tm+1, tr);
            rc->update(x, y, val);
        }
        fix(y);
    }

    ll query(int xl, int xr, int yl, int yr){
        if (xr < tl || tr < xl) return 0;
        if (xl <= tl && tr <= xr) return t->query(yl, yr);
        ll ans = 0;
        if (lc) ans = gcd2(ans, lc->query(xl, xr, yl, yr));
        if (rc) ans = gcd2(ans, rc->query(xl, xr, yl, yr));
        return ans;
    }
};

st* grid;

void init(int R, int C) {
    grid = new st(0, R-1);
}

void update(int P, int Q, ll K){
    grid->update(P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return grid->query(P, U, Q, V);
}

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