제출 #920735

#제출 시각아이디문제언어결과실행 시간메모리
920735NK_The Potion of Great Power (CEOI20_potion)C++17
38 / 100
1025 ms262144 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define f first #define s second #define mp make_pair #define pb push_back #define sz(x) int(x.size()) template<class T> using V = vector<T>; template<class T> using uset = unordered_set<T>; template<class T, size_t SZ> using AR = array<T, SZ>; using vi = V<int>; using pi = pair<int, int>; using vpi = V<pi>; const int BLK = 500; const int INF = 1e9; int N, D; vi H; V<uset<int>> stor[BLK]; uset<int> X, Y; vpi E, C; void init(int n, int d, int h[]) { N = n, D = d; H.resize(N); for(int i = 0; i < N; i++) H[i] = h[i]; } void curseChanges(int U, int A[], int B[]) { V<uset<int>> adj(N); for(int i = 0; i < U; i++) { int u = A[i], v = B[i]; E.pb(mp(u, v)); if (adj[u].count(v)) { adj[u].erase(v); adj[v].erase(u); } else { adj[u].insert(v); adj[v].insert(u); } if (i % BLK == 0) stor[i / BLK] = adj; } } int question(int x, int y, int v) { --v; int B = (v / BLK); X = stor[B][x], Y = stor[B][y]; for(int d = B * BLK + 1; d <= v; d++) { if (E[d].f == x || E[d].s == x) { int z = E[d].f + E[d].s - x; if (X.count(z)) X.erase(z); else X.insert(z); } if (E[d].f == y || E[d].s == y) { int z = E[d].f + E[d].s - y; if (Y.count(z)) Y.erase(z); else Y.insert(z); } } // cout << "X: "; // for(auto& c : X) cout << c << " "; // cout << nl; // cout << "Y: "; // for(auto& c : Y) cout << c << " "; // cout << nl; C = {}; for(auto& c : X) C.pb(mp(H[c], 0)); for(auto& c : Y) C.pb(mp(H[c], 1)); sort(begin(C), end(C)); int ans = INF; for(int i = 0; i + 1 < sz(C); i++) if (C[i].s != C[i + 1].s) ans = min(ans, abs(C[i].f - C[i + 1].f)); 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...