Submission #526747

#TimeUsernameProblemLanguageResultExecution timeMemory
526747joelauOsumnjičeni (COCI21_osumnjiceni)C++14
10 / 110
1069 ms14392 KiB
#include <bits/stdc++.h> using namespace std; int N,Q; pair<int,int> lst[200005]; vector<int> A; set< pair<int,int> > s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N; for (int i = 0; i < N; ++i) { cin >> lst[i].first >> lst[i].second; A.push_back(lst[i].first); A.push_back(lst[i].second); } sort(A.begin(),A.end()); A.resize(unique(A.begin(),A.end())-A.begin()); for (int i = 0; i < N; ++i) { lst[i].first = lower_bound(A.begin(),A.end(),lst[i].first) - A.begin(); lst[i].second = lower_bound(A.begin(),A.end(),lst[i].second) - A.begin(); } cin >> Q; while (Q--) { int l,r; cin >> l >> r; l--, r--; s.clear(); int ans = 1; for (int i = l; i <= r; ++i) { auto it = s.lower_bound(make_pair(lst[i].first,-1)); bool can = true; if (it != s.end() && it->first <= lst[i].second) can = false; if (it != s.begin() && prev(it)->second >= lst[i].first) can = false; if (!can) { ans++; s.clear(); } s.emplace(lst[i].first,lst[i].second).first; } cout << ans << '\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...