Submission #681158

#	Time	Username	Problem	Language	Result	Execution time	Memory
681158		nutella	Game (IOI13_game)	C++17	100 / 100	7299 ms	15156 KiB

game

#pragma GCC optimize("O3")

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

using namespace std;
using ll = long long;

constexpr int MAXQ = 22001;

#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 + 10;

int counter = 1;

ll d[M];

int left[M], right[M];

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

int st_create() {
//    d.emplace_back(), left.emplace_back(), right.emplace_back();
    d[counter] = left[counter] = right[counter] = 0;
    return counter++;
}

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

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) >> 1;

        ll ans = 0;

        if (left[v]) {
            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;
    }
}

void clear(int v) {
    if (!v) return;
    d[v] = 0;
    clear(left[v]);
    clear(right[v]);
}

constexpr int B = 250;

map<pair<int, int>, ll> mp;

constexpr int maxK = MAXQ / B + 1;

pair<int, int> l[maxK], r[maxK];
int root[maxK], top = 0;
vector<pair<int, int>> keks[maxK];
vector<ll> vals[maxK];

void rebuild() {
    counter = 1;

    top = 0;

    int last_sz = 0;
    for (auto [xx, k]: mp) {
        auto [x, y] = xx;
        if (last_sz == B) {
            last_sz = 0;
        }
        if (last_sz == 0) {
            l[top] = xx;
            r[top] = xx;
            keks[top].clear(), vals[top].clear();
            root[top++] = st_create();
        } else {
            r[top - 1] = xx;
        }
        keks[top - 1].push_back(xx);
        vals[top - 1].push_back(k);
        last_sz += 1;

        st_update(root[top - 1], y, k, 0, C);
    }
}

int last_rebuild = 0;

void insert(pair<int, int> xx, ll k) {
    auto itt = mp.find(xx);
    bool was = false;
    ll last = -1;
    if (itt != mp.end()) {
        was = true;
        last = itt->second;
    }
    mp[xx] = k;

    ++last_rebuild;

    if (last_rebuild == 2 * B) {
        last_rebuild = 0;
        rebuild();
        return;
    }

    int i = -1;
    if (xx >= r[top - 1]) {
        i = top - 1;
    } else if (xx <= l[0]) {
        i = 0;
    } else {
        for (int j = top - 1; j >= 0; --j) {
            if (l[j] <= xx) {
                i = j;
                break;
            }
        }
    }

    assert(i != -1);

    l[i] = min(l[i], xx);
    r[i] = max(r[i], xx);


    if (!was) {
        auto it = std::lower_bound(keks[i].begin(), keks[i].end(), xx);
        vals[i].insert(vals[i].begin() + (it - keks[i].begin()), k);
        keks[i].insert(it, xx);
    }

    auto it = std::lower_bound(keks[i].begin(), keks[i].end(),xx) - keks[i].begin();
    vals[i][it] = k;

    if (was) {
        clear(root[i]);
        for (int ii = 0; ii < keks[i].size(); ++ii) {
            st_update(root[i], keks[i][ii].second, vals[i][ii], 0, C);
        }
    } else {
        st_update(root[i], xx.second, k, 0, C);
    }
}

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

    l[0] = {R + 1, C + 1}, r[0] = {0, 0};
    root[top++] = st_create();
}

void update(int P, int Q, ll K) {
    insert({P, Q}, K);
}

ll calculate(int P, int Q, int U, int V) {
    ll cd = 0;
//    pair<int, int> min_done = {U, V + 1};
//    pair<int, int> max_done = {P, Q - 1};
    int fi = 0, la = 0;
    for (int i = 0; i < top; ++i) {
        if (l[i].first >= P && r[i].first <= U) {
            cd = gcd(cd, st_query(root[i], Q, V + 1, 0, C));
//            min_done = min(min_done, l[i]);
//            max_done = max(max_done, r[i]);
        } else {
            if (l[i] <= pair{P, Q} && r[i] >= pair{P, Q}) {
                fi = i;
            }
            if (l[i] <= pair{U, V} && r[i] >= pair{U, V}) {
                la = i;
            }
        }
    }
    if (la == fi) la = -1;
    for (int k : {la, fi}) {
        if (k != -1) {
            for (int i = 0; i < keks[k].size(); ++i) {
                if (keks[k][i].first >= P && keks[k][i].first <= U && keks[k][i].second >= Q && keks[k][i].second <= V) {
                    cd = gcd(cd, vals[k][i]);
                }
            }
        }
    }

    return cd;
}

Compilation message (stderr)

game.cpp: In function 'void insert(std::pair<int, int>, ll)':
game.cpp:182:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         for (int ii = 0; ii < keks[i].size(); ++ii) {
      |                          ~~~^~~~~~~~~~~~~~~~
game.cpp:136:8: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  136 |     ll last = -1;
      |        ^~~~
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:223:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |             for (int i = 0; i < keks[k].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~

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