Submission #1230160

#TimeUsernameProblemLanguageResultExecution timeMemory
1230160RakhimovAmirThe Potion of Great Power (CEOI20_potion)C++20
56 / 100
3080 ms71364 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 1; vector<pair<int, int>> v[4 * N]; set<int> A, B; int h[N], n, U; // void build(int x, int tl, int tr) { // if (tl == tr) { // return; // } // int tm = (tl + tr) / 2; // build(2 * x, tl, tm); // build(2 * x + 1, tm + 1, tr); // } void dfs(int x, int tl, int tr) { sort(v[x].begin(), v[x].end()); if (tl == tr) return; int tm = (tl + tr) / 2; dfs(2 * x, tl, tm); dfs(2 * x + 1, tm + 1, tr); } void add(int x, int tl, int tr, int l, int r, int a, int b) { if (r < tl || l > tr) return; if (l <= tl && r >= tr) { v[x].push_back({a, b}); v[x].push_back({b, a}); return; } int tm = (tl + tr) / 2; add(2 * x, tl, tm, l, r, a, b); add(2 * x + 1, tm + 1, tr, l, r, a, b); } void go(int x, int tl, int tr, int T, int a, int b) { auto i = lower_bound(v[x].begin(), v[x].end(), make_pair(a, -1)) - v[x].begin(); for (; i < v[x].size(); i++) { if (v[x][i].first != a) break; A.insert(h[v[x][i].second]); } i = lower_bound(v[x].begin(), v[x].end(), make_pair(b, -1)) - v[x].begin(); for (; i < v[x].size(); i++) { if (v[x][i].first != b) break; B.insert(h[v[x][i].second]); } if (tl == tr) { return; } int tm = (tl + tr) / 2; if (T <= tm) go(2 * x, tl, tm, T, a, b); else go(2 * x + 1, tm + 1, tr, T, a, b); } void init(int N, int D, int H[]) { n = N; for (int i = 0; i < N; i++) { h[i] = H[i]; } } void curseChanges(int U, int A[], int B[]) { map<pair<int, int>, int> open; ::U = U; // build(1, 0, U); for (int i = 0; i < U; i++) { if (A[i] > B[i]) swap(A[i], B[i]); if (open[{A[i], B[i]}]) { add(1, 0, U, open[{A[i], B[i]}], i, A[i], B[i]); open[{A[i], B[i]}] = 0; } else { open[{A[i], B[i]}] = i + 1; } } for (auto i : open) { if (i.second) { add(1, 0, U, i.second, U, i.first.first, i.first.second); } } dfs(1, 0, U); } int question(int x, int y, int v) { int res = 1e9; go(1, 0, U, v, x, y); if (A.empty() || B.empty()) { A.clear(); B.clear(); return res; } // cou t << "X: " << s[x].size() << " Y: " << s[y].size() << " V: " << v << "\n"; for (auto i : A) { auto r = B.lower_bound(i); if (r != B.end()) { res = min(res, abs(i - *r)); } if (r != B.begin()) { r--; res = min(res, abs(i - *r)); } } A.clear(); B.clear(); return res; }
#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...