Submission #1126192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126192		blackslex	Game (IOI13_game)	C++20	10 / 100	13097 ms	321536 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 {
    vector<ll> t;
    void init (int c) {
        t.resize((c + 5) * 4);
    }
    void upd (int l, int r, int idx, int pos, ll val) {
        if (l == r) return void(t[idx] = val);
        int mid = (l + r) >> 1;
        if (pos <= mid) upd(l, mid, idx * 2 + 1, pos, val);
        else upd(mid + 1, r, idx * 2 + 2, pos, val);
        t[idx] = gcd2(t[idx * 2 + 1], t[idx * 2 + 2]);
    }
    ll qr (int l, int r, int idx, int tl, int tr) {
        if (l > tr || r < tl) return 0;
        if (l >= tl && r <= tr) return t[idx];
        int mid = (l + r) >> 1;
        return gcd2(qr(l, mid, idx * 2 + 1, tl, tr), qr(mid + 1, r, idx * 2 + 2, tl, tr));
    }
};

struct segment2 {
    vector<segment> t;
    void init (int r, int c) {
        t.resize((r + 5) * 4);
        for (int i = 0; i < t.size(); i++) t[i].init(c);
    }
    ll get (segment t, int posy) {
        return t.qr(0, c - 1, 0, posy, posy);
    }
    void upd (int l, int r, int idx, int posx, int posy, ll val) {
        if (l < r) {
            int mid = (l + r) >> 1;
            if (posx <= mid) upd(l, mid, idx * 2 + 1, posx, posy, val);
            else upd(mid + 1, r, idx * 2 + 2, posx, posy, val);
            val = gcd2(get(t[idx * 2 + 1], posy), get(t[idx * 2 + 2], posy));
        }
        t[idx].upd(0, c - 1, 0, posy, val);
    }
    ll qr (int l, int r, int idx, int tlx, int trx, int tly, int _try) {
        if (l > trx || r < tlx) return 0;
        if (l >= tlx && r <= trx) return t[idx].qr(0, c - 1, 0, tly, _try);
        int mid = (l + r) >> 1;
        return gcd2(qr(l, mid, idx * 2 + 1, tlx, trx, tly, _try), qr(mid + 1, r, idx * 2 + 2, tlx, trx, tly, _try));
    }
} segm;

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

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

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

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