Submission #854309

#TimeUsernameProblemLanguageResultExecution timeMemory
854309MisterReaperOsumnjičeni (COCI21_osumnjiceni)C++17
110 / 110
338 ms40528 KiB
//author: Ahmet Alp Orakci #include <bits/stdc++.h> using namespace std; using i64 = long long; bool intersect(int l1, int l2, int r1, int r2) { if(l2 < r1 || r2 < l1) return false; return true; } #define ONLINE_JUDGE void solve() { int n; cin >> n; vector <array <int, 2>> vec(n +1); for(int i = 1; i <= n; i++) { cin >> vec[i][0] >> vec[i][1]; } vector <vector <int>> bl(n +2); for(int i = 1; i <= n +1; i++) bl[i].resize(21); multiset <pair <int, int>> ms; int l = 1, r = 1; ms.emplace(vec[l][0], vec[l][1]); while(l <= n) { if(r < l) { ms.emplace(vec[l][0], vec[l][1]); r++; continue; } auto ok = [&](int x) -> bool { bool res = true; auto it = ms.lower_bound({vec[x][0], 0}); if(it != ms.end()) { auto [a, b] = *it; res &= !intersect(a, b, vec[x][0], vec[x][1]); } if(it != ms.begin()) { auto [a, b] = *prev(it); res &= !intersect(a, b, vec[x][0], vec[x][1]); } return res; }; while(r +1 <= n && ok(r +1)) { r++; ms.emplace(vec[r][0], vec[r][1]); } //cerr << l << " " << r << "\n"; bl[l][0] = r +1; ms.erase(ms.find({vec[l][0], vec[l][1]})); l++; } bl[n +1][0] = n +1; for(int i = 1; i < 21; i++) { for(int j = 1; j <= n +1; j++) { bl[j][i] = bl[bl[j][i -1]][i -1]; } } auto get = [&](int l, int r) -> int { int res = 0; for(int i = 20; i >= 0; i--) { if(bl[l][i] <= r) { l = bl[l][i]; res += (1 << i); } } return res +1; }; int q; cin >> q; while(q--) { int l, r; cin >> l >> r; cout << get(l, r) << "\n"; } return; } signed main() { #ifndef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } 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...