oj.uz

Submission #540120

# Submission time Handle Problem Language Result Execution time Memory
540120 2022-03-19T09:34:49 Z yuto1115 The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 56356 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;
    set<int> sa = gs[v / bc][x], sb = gs[v / bc][y];
    rep2(i, now, v) {
        if (a[i] == x or b[i] == x) {
            if (b[i] == x)
                swap(a[i], b[i]);
            if (sa.count(b[i]))
                sa.erase(b[i]);
            else
                sa.insert(b[i]);
        }
        if (a[i] == y or b[i] == y) {
            if (b[i] == y)
                swap(a[i], b[i]);
            if (sb.count(b[i]))
                sb.erase(b[i]);
            else
                sb.insert(b[i]);
        }
    }
    assert(SZ(sa) <= d);
    assert(SZ(sb) <= d);
    int ans = 1000000000;
    if (sa.empty() or sb.empty())
        return ans;
    auto it = sb.begin();
    for (int i : sa) {
        while (it != sb.end() and *it < i)
            ++it;
        if (it != sb.begin())
            chmin(ans, h[i] - h[*prev(it)]);
        if (it == sb.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 3 ms 592 KB Output is correct
2 Correct 5 ms 668 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 39 ms 15696 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 56236 KB Output is correct
2 Correct 358 ms 56280 KB Output is correct
3 Correct 208 ms 18676 KB Output is correct
4 Correct 1698 ms 22280 KB Output is correct
5 Correct 665 ms 42224 KB Output is correct
6 Execution timed out 3023 ms 29268 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 3792 KB Output is correct
2 Correct 778 ms 2000 KB Output is correct
3 Execution timed out 3065 ms 1992 KB Time limit exceeded
4 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 3 ms 592 KB Output is correct
3 Correct 5 ms 668 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 39 ms 15696 KB Output is correct
6 Correct 360 ms 56236 KB Output is correct
7 Correct 358 ms 56280 KB Output is correct
8 Correct 208 ms 18676 KB Output is correct
9 Correct 1698 ms 22280 KB Output is correct
10 Correct 665 ms 42224 KB Output is correct
11 Execution timed out 3023 ms 29268 KB Time limit exceeded
12 Halted 0 ms 0 KB -