Submission #866794

#TimeUsernameProblemLanguageResultExecution timeMemory
866794sleepntsheepOsumnjičeni (COCI21_osumnjiceni)C++17
10 / 110
318 ms11020 KiB
#include <iostream> #include <cstring> #include <vector> #include <algorithm> #include <deque> #include <set> #include <utility> #include <array> using namespace std; #define ALL(x) x.begin(), x.end() using ll = long long; #define N 200005 int n, q, dep[N], jmp[N], par[N], t[N<<2], lz[N<<2]; pair<int, int> a[N]; void compress() { vector<int> C; for (int i = 0; i < n; ++i) C.push_back(a[i].first), C.push_back(a[i].second); sort(ALL(C)); C.erase(unique(ALL(C)), C.end()); for (int i = 0; i < n; ++i) a[i].first = lower_bound(ALL(C), a[i].first) - C.begin(), a[i].second = lower_bound(ALL(C), a[i].second) - C.begin(); } void push(int v, int l, int r) { if (lz[v] < 1e9) { t[v] = lz[v]; int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; if (l != r) lz[vl] = lz[v], lz[vr] = lz[v]; lz[v] = 1e9; } } void update(int v, int l, int r, int x, int y, int k) { push(v, l, r); if (r < x || y < l) return; if (x <= l && r <= y) { lz[v] = k; push(v, l, r); return; } int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; update(vl, l, m, x, y, k), update(vr, m+1, r, x, y, k); t[v] = min(t[vl], t[vr]); } int query(int v, int l, int r, int x, int y) { push(v, l, r); if (r < x || y < l) return 1e9+86; if (x <= l && r <= y) return t[v]; int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; return min(query(vl, l, m, x, y), query(vr, m+1, r, x, y)); } void init() { memset(t, 63, sizeof t), memset(lz, 63, sizeof lz); cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second; compress(); par[n] = n; dep[n] = 0; jmp[n] = n; for (int i = n; i--;) { par[i] = query(0, 0, 2*n, a[i].first, a[i].second); update(0, 0, 2*n, a[i].first, a[i].second, i); par[i] = min(par[i], par[i+1]); dep[i] = dep[par[i]] + 1; if (dep[par[i]] - dep[jmp[par[i]]] == dep[jmp[par[i]]] - dep[jmp[jmp[par[i]]]]) jmp[i] = jmp[jmp[par[i]]]; else jmp[i] = par[i]; } } void answer() { cin >> q; for (int x, y, z; q--;) { cin >> x >> y, --x, --y, z = dep[x]; for (; x <= y;) { if (dep[jmp[x]] <= dep[y]) x = jmp[x]; else x = par[x]; } cout << z - dep[x] << '\n'; } } int main() { init(); answer(); return 0; }
#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...