Submission #969267

#TimeUsernameProblemLanguageResultExecution timeMemory
969267tsetThe Potion of Great Power (CEOI20_potion)C++14
0 / 100
120 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int, int> const int INF = 1e9; int nbElem, nbVoisinsMax, nbDays; vector<int > alti; const int SQRTDAY = 100; vector<set<int > > save[SQRTDAY *200]; vector<set<int > > voisins; vector<int > Us, Vs; void init(int N, int D, int F[]) { nbElem = N; nbVoisinsMax = D; alti.resize(N); for(int i=0; i<SQRTDAY *2; i++) { save[i].resize(N); } voisins.resize(N); for(int i=0; i< N; i++) { alti[i] = F[i]; } } void curseChanges(int U, int A[], int B[]) { nbDays = U; for(int iDay = 0; iDay < nbDays; iDay++) { if(iDay%SQRTDAY == 0) { save[iDay/SQRTDAY] = voisins; } int u = A[iDay]; int v = B[iDay]; if(voisins[u].find(v) != voisins[u].end()) { voisins[u].erase(v); voisins[v].erase(u); } else { voisins[u].insert(v); voisins[v].insert(u); } Us.push_back(A[iDay]); Vs.push_back(B[iDay]); printf("[%d/%d/%d]\n", iDay,A[iDay], B[iDay]); } } int question(int X, int Y, int V) { V--; int day = V; set<int> vx, vy; int backupDate = day/SQRTDAY; vx = save[backupDate][X]; vy = save[backupDate][Y]; for(int dayRecover = backupDate*SQRTDAY; dayRecover<= day; dayRecover++) { int u = Us[dayRecover]; int v = Vs[dayRecover]; //printf("[%lld/%lld]\n", u, v); if(u == X) { if(vx.find(v) != vx.end()) vx.erase(v); else vx.insert(v); } if(v == X) { if(vx.find(u) != vx.end()) vx.erase(u); else vx.insert(u); } if(u == Y) { if(vy.find(v) != vy.end()) vy.erase(v); else vy.insert(v); } if(v == Y) { if(vy.find(u) != vy.end()) vy.erase(u); else vy.insert(u); } } int ans = INF; vector<pii > altis; for(int valX : vx) { altis.push_back({alti[valX], 0}); } for(int valY: vy) { altis.push_back({alti[valY], 1}); } sort(altis.begin(), altis.end()); vector<int> lasts(2, -INF); for(pii altiAct : altis) { lasts[altiAct.second] = altiAct.first; ans= min(ans, abs(lasts[0] - lasts[1])); } if(ans == INF) return 1000000000; 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...