Submission #1230095

#TimeUsernameProblemLanguageResultExecution timeMemory
1230095GrayThe Potion of Great Power (CEOI20_potion)C++20
38 / 100
2031 ms327680 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <algorithm> #include <bits/stdc++.h> using namespace std; #define ll int #define ff first #define ss second vector<int> h; int n, mxd, d; vector<array<int, 2>> e; int B=1000; vector<vector<vector<int>>> tA; void init(int N, int D, int H[]) { n=N; mxd=D; h.resize(n); for (int i=0; i<n; i++) h[i]=H[i]; } void curseChanges(int U, int u[], int v[]) { vector<set<ll>> A(n); e.resize(U); tA.push_back(vector<vector<int>>(n)); for (ll i=0; i<U; i++){ e[i] = {u[i], v[i]}; if (A[u[i]].count(v[i])){ A[u[i]].erase(v[i]); A[v[i]].erase(u[i]); }else{ A[u[i]].insert(v[i]); A[v[i]].insert(u[i]); } if ((i+1)%B==0){ tA.push_back(vector<vector<int>>(n)); for (ll j=0; j<n; j++){ for (auto x:A[j]) tA.back()[j].push_back(x); } } } } vector<int> hs; set<ll> nodes; int question(int x, int y, int v) { hs.clear(); nodes.clear(); for (auto u:tA[v/B][x]) nodes.insert(u); for (ll i=(v/B)*B; i<v; i++){ if (e[i][0]==x or e[i][1]==x){ if (e[i][1]==x) swap(e[i][0], e[i][1]); if (nodes.count(e[i][1])) nodes.erase(e[i][1]); else nodes.insert(e[i][1]); } } for (auto u:nodes) { hs.push_back(h[u]); } if (hs.empty()) return 1e9; sort(hs.begin(), hs.end()); hs.erase(unique(hs.begin(), hs.end()), hs.end()); nodes.clear(); for (auto u:tA[v/B][y]) nodes.insert(u); for (ll i=(v/B)*B; i<v; i++){ if (e[i][0]==y or e[i][1]==y){ if (e[i][1]==y) swap(e[i][0], e[i][1]); if (nodes.count(e[i][1])) nodes.erase(e[i][1]); else nodes.insert(e[i][1]); } } int mn=1e9; for (auto u:nodes){ ll ind = lower_bound(hs.begin(), hs.end(), h[u])-hs.begin(); if (ind<(ll)hs.size()){ mn=min(mn, hs[ind]-h[u]); } if (ind){ mn=min(mn, h[u]-hs[ind-1]); } } return mn; }
#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...