Submission #1126196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126196		blackslex	Game (IOI13_game)	C++20	63 / 100	1983 ms	278884 KiB

game

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

using namespace std;
using ll = long long;

int r, c;

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 segment {
    struct node {
        ll val;
        node *l, *r;
        node() : val(0), l(nullptr), r(nullptr) {}
    };
    typedef node* pnode;
    pnode rt;
    segment() : rt(nullptr) {}
    void upd (int l, int r, pnode &cur, int pos, ll val) {
        if (!cur) cur = new node();
        if (l == r) return void(cur->val = val);
        int mid = (l + r) >> 1;
        if (pos <= mid) upd(l, mid, cur->l, pos, val);
        else upd(mid + 1, r, cur->r, pos, val);
        cur->val = gcd2(cur->l ? cur->l->val : 0, cur->r ? cur->r->val : 0);
    }
    ll qr (int l, int r, pnode cur, int tl, int tr) {
        if (l > tr || r < tl || !cur) return 0;
        if (l >= tl && r <= tr) return cur->val;
        int mid = (l + r) >> 1;
        return gcd2(qr(l, mid, cur->l, tl, tr), qr(mid + 1, r, cur->r, tl, tr));
    }
};

struct segment2 {
    struct node {
        segment val;
        node *l, *r;
        node() : val(segment()), l(nullptr), r(nullptr) {}
    };
    typedef node* pnode;
    pnode rt;
    segment2() : rt(nullptr) {}
    ll get (pnode t, int posy) {
        return t ? t->val.qr(0, c - 1, t->val.rt, posy, posy) : 0;
    }
    void upd (int l, int r, pnode &cur, int posx, int posy, ll val) {
        if (!cur) cur = new node();
        if (l < r) {
            int mid = (l + r) >> 1;
            if (posx <= mid) upd(l, mid, cur->l, posx, posy, val);
            else upd(mid + 1, r, cur->r, posx, posy, val);
            val = gcd2(get(cur->l, posy), get(cur->r, posy));
        }
        cur->val.upd(0, c - 1, cur->val.rt, posy, val);
    }
    ll qr (int l, int r, pnode cur, int tlx, int trx, int tly, int _try) {
        if (l > trx || r < tlx || !cur) return 0;
        if (l >= tlx && r <= trx) return cur->val.qr(0, c - 1, cur->val.rt, tly, _try);
        int mid = (l + r) >> 1;
        return gcd2(qr(l, mid, cur->l, tlx, trx, tly, _try), qr(mid + 1, r, cur->r, tlx, trx, tly, _try));
    }
} segm;

void init(int R, int C) {
    r = R; c = C;
    /* ... */
}

void update(int P, int Q, long long K) {
    segm.upd(0, r - 1, segm.rt, P, Q, K);
    /* ... */
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return segm.qr(0, r - 1, segm.rt, P, U, Q, V);
}

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