Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5;
- const int INF = 105000;
- int a[N];
- int blocksz, k;
- int blocks[N];
- int n, cnt = 0, m = INF, cur;
- int num(int x) {
- return x / blocksz;
- }
- int get(int l, int r) {
- int m = 0;
- for (int i = l; i <= r; i++) {
- if (i == blocksz * num(i) && i + blocksz < r) {
- m = max(m, blocks[num(i)]);
- i += blocksz - 1;
- } else {
- m = max(m, a[i]);
- }
- }
- return m;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- blocksz = sqrt((double)n);
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- cin >> k;
- vector< pair <int, int> > pairs(k);
- for (int i = 0; i < k; i++) {
- int x, y;
- cin >> x >> y;
- pairs[i].first = x, pairs[i].second = y;
- }
- for (int i = 0; i < n; i++) {
- int c = num(i);
- blocks[c] = max(blocks[c], a[i]);
- }
- for (int i = 0; i < k; i++) {
- int l = pairs[i].first - 1, r = pairs[i].second - 1;
- cout << get(l, r) << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement