Submission #863002

#TimeUsernameProblemLanguageResultExecution timeMemory
8630023omar_ahmedOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
49 ms36336 KiB
#include <bits/stdc++.h> using namespace std ; #define int long long #define endl '\n' #define all(a) a.begin() , a.end() #define alr(a) a.rbegin() , a.rend() signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n; cin >> n; vector < pair < int , int >> a(n); for(int i = 0 ; i < n ; i++) { cin >> a[i].first >> a[i].second; } vector < vector < int >> nxt(20, vector < int > (n + 1, n)); for(int i = 0 ; i < n ; i++) { int nxtt = i; int L = a[i].first, R = a[i].second; for(int j = i + 1 ; j < n ; j++) { int l = max(L, a[j].first); int r = min(R, a[j].second); if(l <= r) { break; } nxtt = j; L = min(L, a[j].first); R = max(R, a[j].second); } nxt[0][i] = nxtt; } for(int i = 1 ; i < 20 ; i++) { for(int j = 0 ; j < n ; j++) { if(nxt[i - 1][j] != n) nxt[i][j] = nxt[i - 1][nxt[i - 1][j] + 1]; } } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; l -= 1, r -= 1; int ans = 0; for(int i = 19 ; i >= 0 ; i--) { if(nxt[i][l] <= r) { ans += (1ll << i); l = nxt[i][l] + 1; } } ans += (l <= r); 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...