Submission #1191831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191831		peteza	Game (IOI13_game)	C++20	0 / 100	1 ms	328 KiB

game

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

struct node1d {
    ll cgcd = 0;
    node1d *l = 0, *r = 0;
    node1d() {}
};

struct node2d {
    node2d *l = 0, *r = 0;
    node1d *seg = 0;
    node2d() {}
} *root;

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;
}

int R, C;

void upd1d(node1d *&cur, int l, int r, int tgt, ll val) {
    if(!cur) cur = new node1d();
    if(l == r) {
        cur->cgcd = val;
        return ;
    }
    int mid = (l+r) >> 1;
    if(tgt <= mid) upd1d(cur->l, l, mid, tgt, val);
    else upd1d(cur->r, mid+1, r, tgt, val);
    cur->cgcd = gcd2(cur->l ? cur->l->cgcd : 0, cur->r ? cur->r->cgcd: 0);
}

void upd2d(node2d *&cur, int l, int r, int tl, int tr, ll val) {
    if(!cur) cur = new node2d();
    if(l == r) {
        upd1d(cur->seg, 0, C-1, tr, val);
        return ;
    }
    int mid = (l+r) >> 1;
    if(tl <= mid) upd2d(cur->l, l, mid, tl, tr, val);
    else upd2d(cur->r, mid+1, r, tl, tr, val);
    upd1d(cur->seg, 0, C-1, tr, val);
}

ll qr1d(node1d*&cur, int l, int r, int tl, int tr) {
    if(!cur) return 0;
    if(tr < l || r < tl) return 0;
    if(tl <= l && r <= tr) return cur->cgcd;
    int mid = (l+r) >> 1;
    return gcd2(qr1d(cur->l, l, mid, tl, tr), qr1d(cur->r, mid+1, r, tl, tr));
}

ll qr2d(node2d *&cur, int l, int r, int tl1, int tr1, int tl2, int tr2) {
    if(!cur) return 0;
    if(tl1 <= l && r <= tr1) return qr1d(cur->seg, 0, C-1, tl2, tr2);
    if(tr1 < l || r < tl1) return 0;
    int mid = (l+r) >> 1;
    return gcd2(qr2d(cur->l, l, mid, tl1, tr1, tl2, tr2), qr2d(cur->r, mid+1, r, tl1, tr1, tl2, tr2));
}

void init(int R, int C) {
    /* ... */
    ::R = R; ::C = C;
    root = 0;
}

void update(int P, int Q, long long K) {
    /* ... */
    upd2d(root, 0, R-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return qr2d(root, 0, R-1, P, U, Q, V);
}

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