Submission #681061

#	Time	Username	Problem	Language	Result	Execution time	Memory
681061		nutella	Game (IOI13_game)	C++17	80 / 100	2941 ms	256000 KiB

game

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

using namespace std;
using ll = long long;

constexpr int MAXQ = 22000;

#define left lft
#define right rght
#define gcd my_gcd

ll my_gcd(ll a, ll b) {
    if (!a || !b) return a ^ b;
    ll c;
    while ((c = a % b)) {
        a = b;
        b = c;
    }
    return b;
}

int R, C;

constexpr int M = MAXQ * 30 * 30 + 10;

int counter = 1;

ll d[M];

int left[M], right[M];

//vector<ll> d{{}};
//vector<int> left{{}}, right{{}};

int st_create(int l, int r) {
//    d.emplace_back(), left.emplace_back(), right.emplace_back();

    return counter++;
}

int pa[30];

void st_update(int v, int i, ll k, int l, int r) {
    int kek = 0;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        pa[kek++] = v;
        if (i < mid) {
            if (!left[v]) {
                left[v] = st_create(l, mid);
            }
            v = left[v];
            r = mid;
        } else {
            if (!right[v]) {
                right[v] = st_create(mid, r);
            }
            v = right[v];
            l = mid;
        }
    }
    d[v] = k;
    for (int x = kek - 1; x >= 0; --x) {
        v = pa[x];
        d[v] = gcd(d[left[v]], d[right[v]]);
    }
}

ll st_query(int v, int lx, int rx, int l, int r) {
    if (lx >= r || rx <= l) {
        return 0;
    } else if (lx <= l && r <= rx) {
        return d[v];
    } else {
        int mid = (l + r) / 2;

        ll ans = 0;

        if (left[v]) {
            ans = gcd(ans, st_query(left[v], lx, rx, l, mid));
        }
        if (right[v]) {
            ans = gcd(ans, st_query(right[v], lx, rx, mid, r));
        }

        return ans;
    }
}

ll st_query_simple(int v, int i, int l, int r) {
    while (l + 1 < r && v) {
        int mid = (l + r) / 2;
        
        if (i < mid) {
            v = left[v];
            r = mid;
        } else {
            v = right[v];
            l = mid;
        }
    }
    return d[v];
}

struct SegmentTree {
    int st = 0;

    int left = 0, right = 0;
};

constexpr int N = MAXQ * 30 + 10;

SegmentTree t[N];

//vector<SegmentTree> t{{}};

int node_counter = 1;

int create(int l, int r) {
//    t[node_counter] = SegmentTree({l, r});
//    t.emplace_back();
    return node_counter++;
}

void build_st(int x) {
    if (!t[x].st) {
        t[x].st = st_create(0, C);
    }
}

ll simple_query(int x, int y) {
    if (!t[x].st) {
        return 0;
    } else {
        return st_query_simple(t[x].st, y, 0, C);
    }
}

void update(int v, int x, int y, ll k, int l, int r) {
    build_st(v);

    if (l + 1 == r) {
        st_update(t[v].st, y, k, 0, C);
    } else {
        int mid = (l + r) / 2;

        if (x < mid) {
            if (!t[v].left) {
                t[v].left = create(l, mid);
            }

            update(t[v].left, x, y, k, l, mid);
        } else {
            if (!t[v].right) {
                t[v].right = create(mid, r);
            }

            update(t[v].right, x, y, k, mid, r);
        }

        st_update(t[v].st, y, gcd(simple_query(t[v].left, y), simple_query(t[v].right, y)), 0, C);
    }
}

ll query(int v, int lx, int rx, int ly, int ry, int l, int r) {
    if (l >= rx || lx >= r || !t[v].st) {
        return 0;
    } else if (lx <= l && r <= rx) {
        return st_query(t[v].st, ly, ry, 0, C);
    } else {
        int mid = (l + r) / 2;

        ll ans = 0;

        if (t[v].left) {
            ans = gcd(ans, query(t[v].left, lx, rx, ly, ry, l, mid));
        }
        if (t[v].right) {
            ans = gcd(ans, query(t[v].right, lx, rx, ly, ry, mid, r));
        }

        return ans;
    }
}

void init(int R, int C) {
    ::R = R, ::C = C;

    create(0, R);
}

void update(int P, int Q, ll K) {
    update(1, P, Q, K, 0, R);
}

ll calculate(int P, int Q, int U, int V) {
    return query(1, P, U + 1, Q, V + 1, 0, R);
}

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