Ломоносов отбор 4

/*Сдать решение задачи 4-Измерения температуры
Полный балл:  1
Имя входного файла: input.txt или стандартный поток ввода
Ограничение времени:  1 с
Ограничение реального времени:   5 с
Ограничение памяти:    512M
Задача 4: Измерения температуры
В результате измерения были получены среднедневные температуры за N последовательных дней (1 ≤ N ≤ 10^7)

Иннокентий решил найти максимальную температуру на всех последовательных интервалах длины K (1 ≤ K ≤ 10^4, K ≤ N). То есть на отрезках [0..K-1], [1..K], [2..K+1] и т.д.

.
Результаты поисков не понравились Иннокентию, поэтому он решил расширить слева и справа каждый i-й отрезок на li, ri соответственно. Считайте, что если при этом происходит выход за границы исходной последовательности, то числа там -inf.

На стандартном потоке вводится число N и N чисел задаюших последовательность измерений. Затем K - длина отрезка поиска, затем N-K+1 пары положительных чисел не больших 1000 и не больших K - li, ri соответственно.

Для каждого из N-K+1 отрезков длины K c соответствующими расширениями выведите максимум на них

Примеры
Входные данные
10
1 2 3 1 3   7 8 5 3 1
3
0 1
1 1
0 1
0 0
0 0
0 0
0 0
1 0
Результат работы
3
3
7
7
8
8
8
8*/


#include<iostream>
#include<fstream>
#include<vector>
#include<stdint.h>
#include<algorithm>
#include<cmath>
#define all(container) container.begin(), container.end()
#define fors(counter, start, finish) for (int counter = start; counter < finish; ++counter)
#define forb(counter, start, finish) for (int counter = start; counter >= finish; --counter)
#define vec(type) std::vector<type>
#define dvec(type) std::vector<std::vector<type>>
//#define fin std::cin

int main() {
    std::ifstream fin("input.txt");
    int n; fin >> n;
    vec(int) t(n);
    fors(i, 0, n)
        fin >> t[i];
    int k; fin >> k;
    std::vector<std::pair<int, int>> idx(n);
    fors(i, 0, n)
        fin >> idx[i].first >> idx[i].second;
    fors(i, 0, n - k + 1) {
        int ldx = i - idx[i].first, rdx = i + k + idx[i].second;
        int res = 0;
        fors(j, (ldx < 0 ? 0 : ldx), (rdx < t.size() ? rdx : t.size())) {
            res = std::max(res, t[j]);
        }
        std::cout << res << std::endl;
    }
    return 0;
}



#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<stdint.h>
#include<algorithm>
#define all(container) container.begin(), container.end()
#define fors(counter, start, finish) for (int counter = start; counter < finish; ++counter)
#define forb(counter, start, finish) for (int counter = start; counter >= finish; --counter)
#define vec(type) std::vector<type>
#define dvec(type) std::vector<std::vector<type>>
//#define fin std::cin

using namespace std;

const int MAXN = 10000000;
pair<int, int> t[4 * MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first)
        return a;
    if (b.first > a.first)
        return b;
    return make_pair(a.first, a.second + b.second);
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr)
        t[v] = make_pair(a[tl], 1);
    else {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}

pair<int, int> get_max(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return make_pair(-100000000, 0);
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(
        get_max(v * 2, tl, tm, l, min(r, tm)),
        get_max(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)
    );
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        t[v] = make_pair(new_val, 1);
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, new_val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, new_val);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}

int main() {
    std::ifstream fin("input.txt");
    int n; fin >> n;
    int a[MAXN];
    fors(i, 0, n) {
        fin >> a[i];
    }
    int k; fin >> k;
    build(a, 1, 0, n - 1);
    fors(i, 0, n - k + 1) {
        int ldx, rdx;
        fin >> ldx >> rdx;
        int left = max(i - ldx, 0);
        int right = min(i + k + rdx - 1, n - 1);
        auto res = get_max(1, 0, n - 1, left, right);
        std::cout << res.first << std::endl;
    }

    return 0;
}