제출 #540111

#제출 시각아이디문제언어결과실행 시간메모리
540111yuto1115The Potion of Great Power (CEOI20_potion)C++17
17 / 100
3057 ms56328 KiB
// #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]); } } set<int> a = G[x], b = G[y]; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...