Submission #915625

#TimeUsernameProblemLanguageResultExecution timeMemory
915625SalihSahinOsumnjičeni (COCI21_osumnjiceni)C++14
0 / 110
295 ms22292 KiB
#include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; const int mod = 998244353; int main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int n; cin>>n; pair<int, int> a[n]; for(int i = 0; i < n; i++){ cin>>a[i].first>>a[i].second; } int K = 18, r = 0; set<pair<int, int> > op; int lift[K][n+1]; for(int l = 0; l < n; l++){ while(r < n){ bool ok = 1; if(op.size()){ auto it = op.lower_bound(a[r]); if(it != op.end() && (*it).first <= a[r].second) ok = 0; if(it != op.begin()){ it--; if((*it).second >= a[r].first) ok = 0; } } if(ok){ op.insert(a[r]); r++; } else break; } lift[0][l] = r; op.erase(a[l]); cout<<l<<" "<<r<<endl; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q, ans, lq, rq; cin>>q; while(q--){ cin>>lq>>rq; lq--, rq--; ans = 1; for(int i = K-1; i >= 0; i--){ if(lift[i][lq] <= rq){ lq = lift[i][lq]; ans += (1 << i); } } cout<<ans<<endl; } 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...