Submission #948151

#TimeUsernameProblemLanguageResultExecution timeMemory
948151blackavarOsumnjičeni (COCI21_osumnjiceni)C++14
110 / 110
283 ms51796 KiB
#include <bits/stdc++.h> using namespace std; struct doan{ long long l, r; }; long long n; doan arr[1000005]; set <pair<long long, long long>> pi; long long st[200005][18]; bool canInsert(long long pos) { if (pi.empty()) return true; auto it = pi.lower_bound({arr[pos].l, 1e18}); int nxt = it -> second; if (arr[pos].l <= arr[nxt].l && arr[nxt].l <= arr[pos].r) return false; if (it != pi.begin()) { it--; int prv = it -> second; if (arr[prv].l <= arr[pos].l && arr[pos].l <= arr[prv].r) return false; } return true; } void preprocess() { long long lim = 0; for (int i = 1; i <= n; i++) { if (lim < i) { pi.clear(); lim = i; pi.insert({arr[i].l, i}); } while (lim + 1 <= n && canInsert(lim + 1)) { lim++; pi.insert({arr[lim].l, lim}); } st[i][0] = lim + 1; pi.erase({arr[i].l, i}); } st[n + 1][0] = n + 1; for (int i = 1; i < 18; i++) { for (int j = 1; j <= n + 1; j++) { st[j][i] = st[st[j][i - 1]][i - 1]; } } } long long get(long long l, long long r) { long long res = 1; for (int i = 17; i >= 0; i--) { if (st[l][i] <= r) { l = st[l][i]; res += 1 << i; } } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i].l >> arr[i].r; } long long t; cin >> t; preprocess(); while (t--) { long long p, q; cin >> p >> q; cout << get(p, q) << "\n"; } 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...