# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
862312 | 2023-10-18T03:38:41 Z | TAhmed33 | Osumnjičeni (COCI21_osumnjiceni) | C++ | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; int main () { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; pair <int, int> arr[n + 1]; for (int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second; int nxt[n + 1] = {}; nxt[n] = n; for (int i = n - 1; i >= 1; i--) { nxt[i] = n; multiset <pair <int, int>> cur; cur.insert(arr[i]); for (int j = i + 1; j <= n; j++) { auto l = cur.lower_bound({arr[j].second + 1, 0}); if (l == cur.begin()) { cur.insert(arr[j]); continue; } l--; auto x = *l; if (x.second < arr[j].first) { cur.insert(arr[j]); continue; } nxt[i] = j - 1; break; } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int cnt = 1; for (int i = l + 1; i <= r; i++) if (min(r, nxt[i]) != mimn(r, nxt[i - 1])) cnt++; cout << cnt << '\n'; } }