Submission #969265

#TimeUsernameProblemLanguageResultExecution timeMemory
969265tsetThe Potion of Great Power (CEOI20_potion)C++14
0 / 100
134 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<ll, ll> #define ll long long const ll INF = 1e18 + 42; ll nbElem, nbVoisinsMax, nbDays; vector<ll > alti; const ll SQRTDAY = 100; vector<set<ll > > save[SQRTDAY *2]; vector<set<ll > > voisins; vector<ll > Us, Vs; void init(int N, int D, int F[]) { nbElem = N; nbVoisinsMax = D; alti.resize(N); for(ll i=0; i<SQRTDAY *2; i++) { save[i].resize(N); } voisins.resize(N); for(ll i=0; i< N; i++) { alti[i] = F[i]; } } void curseChanges(int U, int A[], int B[]) { nbDays = U; for(ll iDay = 0; iDay < nbDays; iDay++) { if(iDay%SQRTDAY == 0) { save[iDay/SQRTDAY] = voisins; } ll u = A[iDay]; ll 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--; ll day = V; set<ll> vx, vy; ll backupDate = day/SQRTDAY; vx = save[backupDate][X]; vy = save[backupDate][Y]; for(ll dayRecover = backupDate*SQRTDAY; dayRecover<= day; dayRecover++) { ll u = Us[dayRecover]; ll 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); } } ll ans = INF; vector<pii > altis; for(ll valX : vx) { altis.push_back({alti[valX], 0}); } for(ll valY: vy) { altis.push_back({alti[valY], 1}); } sort(altis.begin(), altis.end()); vector<ll> 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; }

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:54:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   54 |         printf("[%d/%d/%d]\n", iDay,A[iDay], B[iDay]);
      |                  ~^            ~~~~
      |                   |            |
      |                   int          long long int
      |                  %lld
#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...