rmq accepted
unknown
c_cpp
25 days ago
1.1 kB
6
Indexable
/* in the name of coder of the world * ANAR * */ #include<iostream> using namespace std; #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); #define endl '\n' int mysq(int n){ int l = 1, r = n/2, mid; while(r - l > 1){ mid = (l+r) / 2; if(mid * mid <= n) l = mid; else r = mid; } return l; } int main(){ ios; int n; cin >> n; int a[n]; for(int i = 0; i < n; i++){ cin >> a[i]; } int bl[n], sq = mysq(n); for(int i = 0; i < n; i++) bl[i] = 2147483647 ; for(int i = 0; i < n; i++){ bl[i/sq] = min(a[i], bl[i/sq]); } int q; cin >> q; while(q--){ int l, r, ans = 2147483647; cin >> l >> r; while(l <= r){ if(!(l % sq) && l + sq <= r){ ans = min(bl[l/sq], ans); l += sq; } else{ ans = min(ans, a[l]); l++; } } cout << ans << endl; } return 0; }
Editor is loading...
Leave a Comment