Submission #972110

#TimeUsernameProblemLanguageResultExecution timeMemory
972110RaresFelixThe Potion of Great Power (CEOI20_potion)C++17
38 / 100
1918 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; using vi = vector<int>; namespace AINTpers { struct nod { int cnt; int l, r; /// indici pt fii in V }; vector<nod> V; int nod_nou() { V.push_back(nod{0, -1, -1}); return int(V.size()) - 1; } int join(int u, int v) { int re = V.size(); V.push_back(V[u]); V[re].cnt = V[u].cnt + V[v].cnt; V[re].l = u; V[re].r = v; return re; } int enable(int u, int p, int st, int dr) { if(u == -1) return -1; if(p < st || dr < p) return u; if(st == dr) { int v = V.size(); V.push_back(V[u]); V[v].cnt = 1; return v; } if(V[u].l == -1) { V[u].l = nod_nou(); V[u].r = nod_nou(); } return join(enable(V[u].l, p, st, (st + dr) >> 1), enable(V[u].r, p, ((st + dr) >> 1) + 1, dr)); } int disable(int u, int p, int st, int dr) { if(u == -1) return -1; if(p < st || dr < p) return u; if(st == dr) { int v = V.size(); V.push_back(V[u]); V[v].cnt = 0; return v; } if(V[u].l == -1) { /// uhhh, nu ar trebuii sa ajungi aici assert(0); /// TODO, check if this is triggered V[u].l = nod_nou(); V[u].r = nod_nou(); } return join(disable(V[u].l, p, st, (st + dr) >> 1), disable(V[u].r, p, ((st + dr) >> 1) + 1, dr)); } int stare(int u, int p, int st, int dr) { if(u == -1) return 0; if(st == dr) return V[u].cnt; int mij = (st + dr) / 2; if(V[u].l == -1) return 0; if(p <= mij) return stare(V[u].l, p, st, mij); return stare(V[u].r, p, mij + 1, dr); } void enumerate(int u, int st, int dr, vi &Re) { if(u == -1 || !V[u].cnt) return; if(st == dr) { Re.push_back(st); return; } enumerate(V[u].l, st, (st + dr) >> 1, Re); enumerate(V[u].r, ((st + dr) >> 1) + 1, dr, Re); } } struct SetPers { int n; vector<ii> Rad; SetPers(int N) : n(N) { Rad.emplace_back(0, AINTpers::nod_nou()); } void update(int t, int p) { int r = Rad.back().second; int a = AINTpers::stare(r, p, 0, n - 1); if(!a) { Rad.push_back({t, AINTpers::enable(r, p, 0, n - 1)}); } else { Rad.push_back({t, AINTpers::disable(r, p, 0, n - 1)}); } } vi list(int t) { auto it = upper_bound(Rad.begin(), Rad.end(), ii{t, 1e9}); --it; int r = it->second; vi Re; AINTpers::enumerate(r, 0, n - 1, Re); return Re; } }; int n; vi H0; vector<SetPers> S; void init(int N, int D, int H[]) { n = N; for(int i = 0; i < n; ++i) H0.push_back(H[i]); for(int i = 0; i < n; ++i) S.push_back(SetPers(N)); } void curseChanges(int U, int A[], int B[]) { for(int i = 1; i <= U; ++i) { int a = A[i - 1], b = B[i - 1]; S[a].update(i, b); S[b].update(i, a); } } const int INF = 1e9; int question(int x, int y, int v) { vi A = S[x].list(v), B = S[y].list(v); vector<ii> V; for(auto it : A) V.push_back(ii{H0[it], -1}); for(auto it : B) V.push_back(ii{H0[it], 1}); sort(V.begin(), V.end()); int re = INF; for(int i = 1; i < V.size(); ++i) { if(V[i].second != V[i - 1].second) re = min(re, V[i].first - V[i - 1].first); } return re; }

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 1; i < V.size(); ++i) {
      |                    ~~^~~~~~~~~~
#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...