oj.uz

Submission #540119

# Submission time Handle Problem Language Result Execution time Memory
540119 2022-03-19T09:28:19 Z yuto1115 The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 56300 KB 
// #include "grader.cpp"
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template <class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> void vecout(const vector<T> &v, char div = '\n') {
    int n = SZ(v);
    rep(i, n) cout << v[i] << (i == n - 1 ? '\n' : div);
}

namespace {
int n, d, u;
vi h, a, b;
vi conv;
int bc;
vector<vector<set<int>>> gs;
} // namespace

void init(int N, int D, int H[]) {
    n = N;
    d = D;
    h = vi(H, H + N);
    vi ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return h[i] < h[j]; });
    conv.resize(n);
    rep(i, n) conv[ord[i]] = i;
    sort(all(h));
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    a = vi(A, A + U);
    b = vi(B, B + U);
    for (int &i : a)
        i = conv[i];
    for (int &i : b)
        i = conv[i];
    // bc = int(sqrt((double)n * u / 50000));
    bc = u;
    chmax(bc, 1);
    gs.reserve(u / bc + 1);
    vector<set<int>> G(n);
    gs.pb(G);
    rep(i, u) {
        if (G[a[i]].count(b[i])) {
            G[a[i]].erase(b[i]);
            G[b[i]].erase(a[i]);
        } else {
            G[a[i]].insert(b[i]);
            G[b[i]].insert(a[i]);
        }
        if ((i + 1) % bc == 0)
            gs.pb(G);
    }
}

int question(int x, int y, int v) {
    x = conv[x], y = conv[y];
    int now = v / bc * bc;
    vector<set<int>> G = gs[now / bc];
    rep2(i, now, v) {
        if (G[a[i]].count(b[i])) {
            G[a[i]].erase(b[i]);
            G[b[i]].erase(a[i]);
        } else {
            G[a[i]].insert(b[i]);
            G[b[i]].insert(a[i]);
        }
    }
    const set<int> &a = G[x], b = G[y];
    assert(SZ(a) <= d);
    assert(SZ(b) <= d);
    int ans = 1000000000;
    if (a.empty() or b.empty())
        return ans;
    auto it = b.begin();
    for (int i : a) {
        while (it != b.end() and *it < i)
            ++it;
        if (it != b.begin())
            chmin(ans, h[i] - h[*prev(it)]);
        if (it == b.end())
            break;
        chmin(ans, h[*it] - h[i]);
    }
    return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 592 KB Output is correct
2 Correct 93 ms 592 KB Output is correct
3 Correct 91 ms 592 KB Output is correct
4 Correct 1047 ms 15796 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3007 ms 56300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 56180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 3792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 95 ms 592 KB Output is correct
3 Correct 93 ms 592 KB Output is correct
4 Correct 91 ms 592 KB Output is correct
5 Correct 1047 ms 15796 KB Output is correct
6 Execution timed out 3007 ms 56300 KB Time limit exceeded
7 Halted 0 ms 0 KB -