Submission #1229986

#TimeUsernameProblemLanguageResultExecution timeMemory
1229986ansoriThe Potion of Great Power (CEOI20_potion)C++17
17 / 100
590 ms315796 KiB
#include<bits/stdc++.h> using namespace std; const int BL = 2500 , UU = 2e5 , NN = 1e5; vector<int> a , b , h; vector<int> g[UU / BL + 1][NN]; set<int> gg[NN]; int n , d; void init(int N, int D, int H[]) { h = vector<int> (N , 0); n = N , d = D; for(int i = 0;i < n; ++ i) h[i] = H[i]; } void curseChanges(int U, int A[], int B[]) { for(int i = 0;i < U; ++ i){ if(A[i] > B[i]) swap(A[i] , B[i]); a.push_back(A[i]); b.push_back(B[i]); if(gg[a[i]].find(b[i]) == gg[a[i]].end()){ gg[a[i]].insert(b[i]); gg[b[i]].insert(a[i]); } else{ gg[a[i]].erase(b[i]); gg[b[i]].erase(a[i]); } if((i + 1) % BL == 0){ for(int i = 0;i < n; ++ i){ for(auto to : gg[i]){ g[(i + 1) / BL][i].push_back(to); } } } } } int question(int x, int y, int v) { if(x > y) swap(x , y); v --; unordered_set<int> vx , vy; for(auto to : g[(v + 1) / BL][x]) vx.insert(to); for(auto to : g[(v + 1) / BL][x]) vy.insert(to); for(int i = (v + 1) / BL * BL;i <= v; ++ i){ //cout << i << ' '; if(a[i] == x or b[i] == x){ int f = a[i] + b[i] - x; if(! vx.count(f)) vx.insert(f); else vx.erase(f); } if(a[i] == y or b[i] == y){ int f = a[i] + b[i] - y; if(! vy.count(f)) vy.insert(f); else vy.erase(f); } } vector<int> hx , hy; //cout << x << ' ' << y << ' '; for(auto to : vx){ //cout << to << ' '; hx.push_back(h[to]); } for(auto to : vy){ //cout << to << ' '; hy.push_back(h[to]); } if(hx.size() == 0 or hy.size() == 0) return 1000000000; sort(hx.begin() , hx.end()); sort(hy.begin() , hy.end()); int j = 0 , answ = 1e9 , s = hy.size(); for(auto to : hx){ while(j < s and hy[j] <= to) j ++; answ = min({answ , abs(to - hy[max(0 , j - 1)]) , abs(to - hy[min(s - 1 , j)])}); } return answ; }
#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...