Submission #493065

#TimeUsernameProblemLanguageResultExecution timeMemory
493065LittleCubeThe Potion of Great Power (CEOI20_potion)C++14
100 / 100
2735 ms184384 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define F first #define S second using namespace std; int N, D, H[100005], U, B, uid[200005], udx; bool mx[200005], my[200005]; pii change[200005]; bool block[2005][200005]; vector<int> v[100005]; vector<int> fri[100005]; map<int, int> mp[100005]; void init(int n, int d, int h[]) { N = n; D = d; for (int i = 0; i < N; i++) H[i] = h[i]; } void curseChanges(int u, int a[], int b[]) { U = u; B = sqrt((U + 1) / 3); for (int i = 0; i < U; i++) { if (a[i] > b[i]) swap(a[i], b[i]); change[i].F = a[i]; change[i].S = b[i]; } for (int i = 0; i < U; i++) if (mp[a[i]].find(b[i]) != mp[a[i]].end()) uid[i] = mp[a[i]][b[i]]; else { mp[a[i]][b[i]] = uid[i] = i; v[a[i]].emplace_back(i); fri[a[i]].emplace_back(b[i]); v[b[i]].emplace_back(i); fri[b[i]].emplace_back(a[i]); } for (int i = 0; i < N; i++) sort(fri[i].begin(), fri[i].end(), [&](int i1, int i2) { return H[i1] < H[i2]; }); for (int i = 1, j = 0; j < U; i++) { for (int k = 0; k < U; k++) block[i][k] = block[i - 1][k]; for (; j < i * B && j < U; j++) block[i][uid[j]] ^= 1; } } int question(int x, int y, int V) { int b = V / B; vector<ll> sx, sy; for (int i : v[x]) if (block[b][i]) { if (change[i].F == x) mx[change[i].S] = 1; else mx[change[i].F] = 1; } for (int i : v[y]) if (block[b][i]) { if (change[i].F == y) my[change[i].S] = 1; else my[change[i].F] = 1; } for (int i = b * B; i < V; i++) { if (change[i].S == x) mx[change[i].F] ^= 1; if (change[i].S == y) my[change[i].F] ^= 1; if (change[i].F == x) mx[change[i].S] ^= 1; if (change[i].F == y) my[change[i].S] ^= 1; } for (ll i : fri[x]) if (mx[i]) sx.emplace_back(H[i]); for (ll i : fri[y]) if (my[i]) sy.emplace_back(H[i]); ll ans = 1e9; while (!sx.empty() && !sy.empty()) { ans = min(ans, abs(sx.back() - sy.back())); if (sx.back() >= sy.back()) sx.pop_back(); else sy.pop_back(); } for (ll i : fri[x]) mx[i] = 0; for (ll i : fri[y]) my[i] = 0; return ans; } /* 6 5 11 4 2 42 1000 54 68 234 0 1 2 0 3 4 3 5 3 5 1 3 5 3 0 5 3 0 1 3 3 5 0 3 4 26 3 0 8 0 0 5 5 1000000000 3 0 11 14 */
#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...