Submission #863039

#TimeUsernameProblemLanguageResultExecution timeMemory
8630393omar_ahmedOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
1069 ms38644 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; n += 1; vector < pair < int , int >> a(n); for(int i = 0 ; i + 1 < n ; i++) { cin >> a[i].first >> a[i].second; } a[n - 1] = {1, n}; vector < vector < int >> nxt(20, vector < int > (n + 1, -1)); for(int i = 0 ; i < n ; i++) { int found = -1; for(int j = i + 1 ; j < n ; j++) { for(int k = i ; k < j ; k++) { int l = max(a[j].first, a[k].first); int r = min(a[j].second, a[k].second); if(l <= r) { found = j - 1; break; } } if(found != -1) { break; } } nxt[0][i] = found; } for(int i = 1 ; i < 20 ; i++) { for(int j = 0 ; j < n ; j++) { if(nxt[i - 1][j] != -1) 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 && nxt[i][l] != -1) { 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...