Submission #1189133

#TimeUsernameProblemLanguageResultExecution timeMemory
1189133lopkusOsumnjičeni (COCI21_osumnjiceni)C++20
10 / 110
1097 ms2768 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::function<int(int, int, int, int)> acs = [] (int l1, int r1, int l2, int r2) { if(l1 > r1) { return 0; } if(l2 > r2) { return 0; } int l = std::max(l1, l2); int r = std::min(r1, r2); if(l > r) { return 0; } return r - l + 1; }; 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(acs(a[i], b[i], a[j], b[j]) > 0) { f = j; break; } } 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...