Submission #1024082

#TimeUsernameProblemLanguageResultExecution timeMemory
1024082vjudge1Osumnjičeni (COCI21_osumnjiceni)C++17
110 / 110
585 ms31184 KiB
// Time: 15-07-2024 16:33:04 // Problem: E - Osumnjičeni // Contest: Virtual Judge - COCI 2021 Contest # 2 // URL: https://vjudge.net/contest/640690#problem/E // Memory Limit: 512 MB // Time Limit: 1000 ms #include <bits/stdc++.h> using namespace std; bool valid(multiset<pair<int,int>> &se,pair<int,int> p) { auto it=se.insert(p); if (it!=se.begin()) { it--; if ((*it).second>=p.first) { se.erase(++it); return 0; } it++; } it++; if (it!=se.end()) { if ((*it).first<=p.second) { se.erase(--it); return 0; } } return 1; } int main() { int n; cin>>n; vector<pair<int,int>> vec; for (int i=0;i<n;i++) { int l,r; cin>>l>>r; vec.push_back({l,r}); } multiset<pair<int,int>> se; int i=0,j=0; int rc[n+1][18]; while (i<n) { if (j<n) { while (j<n && valid(se,vec[j])) j++; } rc[i][0]=j; se.erase(se.find(vec[i])); i++; } for (int i=0;i<18;i++) rc[n][i]=n; for (int p=1;p<18;p++) for (int i=0;i<n;i++) rc[i][p]=rc[rc[i][p-1]][p-1]; int q; cin>>q; while (q--) { int a,b; cin>>a>>b; a--,b--; int ans=1; for (int p=17;p>=0;p--) if (rc[a][p]<=b) ans+=(1<<p),a=rc[a][p]; 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...