oj.uz

Submission #540117

# Submission time Handle Problem Language Result Execution time Memory
540117 2022-03-19T09:24:47 Z yuto1115 The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 3000 ms 112784 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]);
        }
    }
    assert(now == v);
    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.end())
                break;
            chmin(ans, h[*it] - h[i]);
        }
    }
    {
        auto it = b.begin();
        for (int i : a) {
            if (i < *it)
                continue;
            while (next(it) != b.end() and *next(it) <= i)
                ++it;
            chmin(ans, h[i] - h[*it]);
        }
    }
    return ans;
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 507 ms 112784 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6776 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -