Submission #1189136

#TimeUsernameProblemLanguageResultExecution timeMemory
1189136lopkusOsumnjičeni (COCI21_osumnjiceni)C++20
0 / 110
1096 ms2628 KiB
#include <bits/stdc++.h> void solve() { int n; std::cin >> n; std::vector<int> a(n + 1), b(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i] >> b[i]; } std::vector<int> d(n + 2, n + 1); for(int i = n; i >= 1; i--) { int f = n + 1; for(int j = i + 1; j <= n; j++) { if(b[j] >= a[i] && b[j] <= b[i]) { f = std::min(f, j); } if(a[j] >= a[i] && a[j] <= b[i]) { f = std::min(f, j); } } d[i] = std::min(d[i + 1], f); } int q; std::cin >> q; while(q--) { int l, r; std::cin >> l >> r; int now = l; int ans = 0; while(now <= r) { ++ans; now = d[now]; } std::cout << ans << "\n"; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { 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...