Submission #862972

#TimeUsernameProblemLanguageResultExecution timeMemory
8629723omar_ahmedOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
51 ms40404 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)); for(int i = 0 ; i < n ; i++) { int nxtt = n; for(int j = i + 1 ; j < n ; j++) { int l = max(a[i].first, a[j].first); int r = min(a[i].second, a[j].second); if(l <= r) { nxtt = j; break; } } nxt[0][i] = nxtt; } nxt[0][n] = n; for(int i = 1 ; i < 20 ; i++) { nxt[i][n] = n; for(int j = 0 ; j < n ; j++) { nxt[i][j] = nxt[i - 1][nxt[i - 1][j]]; } } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; l -= 1; int ans = 0; for(int i = 19 ; i >= 0 ; i--) { if(nxt[i][l] < r) { ans += (1ll << i); l = nxt[i][l]; } } ans += 1; 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...