Submission #578908

#	Time	Username	Problem	Language	Result	Execution time	Memory
578908		Mazaalai	Game (IOI13_game)	C++17	100 / 100	4484 ms	114192 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define LINE "--------------------\n"
#define pb push_back
using namespace std;
using ll = long long;
int ST1, ST2, ED1, ED2;
ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct SegTree1D {
    int hasOne, child[2];
    ll val;
    SegTree1D() {
        hasOne = val = 0; // 0 means empty, -1 means not empty, hasOne > 0 means id
        child[0] = child[1] = -1;
    }
};
struct SegTree2D {
    int child[2], ptr;
    vector <SegTree1D> node;
    SegTree2D() {
        ptr = 1;
        node.pb(SegTree1D());
        child[0] = child[1] = -1;
    }
    void update2(int l, int r, int id, ll val, int head) {
        if (node[head].hasOne == id || node[head].hasOne == 0) {
            node[head].val = val;
            // cout << "UPDATED1: " << "(" << l << "," << r << ") " << id << " " << val << '\n';
            node[head].hasOne = id;
            return;
        }
        if (node[head].child[0] == -1) {
            node[head].child[0] = ptr++;
            node.pb(SegTree1D());
            node[head].child[1] = ptr++;
            node.pb(SegTree1D());
        }
 
        int mid = (l+r)>>1;
        if (node[head].hasOne > 0) {
            int tmp = node[head].hasOne; node[head].hasOne = -1;
            if (tmp <= mid) update2(l, mid, tmp, node[head].val, node[head].child[0]);
            else update2(mid+1, r, tmp, node[head].val, node[head].child[1]);
        }
        if (id <= mid) update2(l, mid, id, val, node[head].child[0]);
        else update2(mid+1, r, id, val, node[head].child[1]);
        node[head].val = gcd(
            node[ node[head].child[0] ].val,
            node[ node[head].child[1] ].val
        );
        // cout << "LR : " << node[ node[head].child[0] ].val << ',' << node[ node[head].child[1] ].val << '\n';
        // cout << "UPDATED2: " << "(" << l << "," << r << ") " << id << " " << node[head].val << '\n';
    }
    void update2(int id, ll val) {
        update2(ST2, ED2, id, val, 0);
    }
    ll query(int l, int r, int L, int R, int head) {
        if (head == -1 || l > R || L > r || node[head].hasOne == 0) return 0;
        if (node[head].hasOne > 0 && (node[head].hasOne > R || node[head].hasOne < L)) return 0;
        if (node[head].hasOne > 0) return node[head].val;
        if (L <= l && r <= R) return node[head].val;
        int mid = (l+r)>>1;
        return gcd(
            query(l, mid, L, R, node[head].child[0]),
            query(mid+1, r, L, R, node[head].child[1])
        );
    }
    ll query(int l, int r) {
        return query(ST2, ED2, l, r, 0);
    }
    ll query(int id) {
        return query(ST2, ED2, id, id, 0);
    }
};
vector <SegTree2D> node;
int ptr, X1, X2, Y1, Y2;
ll val;
void update1(int l, int r, int head) { // match X
    if (l == r) {
        node[head].update2(Y1, val);
        return;
    }
    if (node[head].child[0] == -1) {
        node[head].child[0] = ptr++;
        node.pb(SegTree2D());
        node[head].child[1] = ptr++;
        node.pb(SegTree2D());
    }
    int mid = (l+r)>>1;
    if (X1 <= mid) {
        update1(l, mid, node[head].child[0]);
    } else {
        update1(mid+1, r, node[head].child[1]);
    }
    ll tmp = gcd(
        node[ node[head].child[0] ].query(Y1), 
        node[ node[head].child[1] ].query(Y1)
    );
    node[head].update2(Y1, tmp);
    return;
}
ll query(int l, int r, int head) {
    if (l > X2 || X1 > r || head == -1) return 0;
    if (X1 <= l && r <= X2) return node[head].query(Y1, Y2);
    int mid = (l+r)>>1;
    return gcd(
        query(l, mid, node[head].child[0]),
        query(mid+1, r, node[head].child[1])
    );
}
void init(int R, int C) {
    ST1 = ST2 = 1;
    ED1 = R;
    ED2 = C;
    ptr = 1;
    node.pb(SegTree2D());
}
 
void update(int x, int y, ll K) {
    x++, y++;
    X1 = x;
    Y1 = y;
    val = K;
    // cout << LINE;
    // cout << "UPDATE: " << x << ' ' << y << ' ' << K << '\n';
    update1(ST1, ED1, 0);
    // for (int i = ST1; i <= ED1; i++)
    // for (int j = ST2; j <= ED2; j++) {
 
    //     X1 = X2 = i;
    //     Y1 = Y2 = j;
    //     cout << query(ST1, ED1, 0) << " \n"[j==3];
    // }
}
 
ll calculate(int x1, int y1, int x2, int y2) {
    x1++, y1++, x2++, y2++;
    X1 = x1;
    Y1 = y1;
    X2 = x2;
    Y2 = y2;
    // cout << "RES: ";
    return query(ST1, ED1, 0);
}

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