Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ο»Ώ#include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- void build(vector<long long>&a, vector<long long>&t, long long v, long long tl, long long tr) {
- if (tl == tr) {
- t[v] = tl;
- return;
- }
- long long tm = (tl + tr) / 2;
- build(a, t, 2 * v, tl, tm);
- build(a, t, 2 * v + 1, tm + 1, tr);
- if (a[t[2 * v]] > a[t[2 * v + 1]]) {
- t[v] = t[2 * v];
- } else {
- t[v] = t[2 * v + 1];
- }
- }
- long long mx(vector<long long>& a, vector<long long>& t, long long v, long long tl, long long tr, long long l, long long r) {
- if (r < l) {
- return a.size() - 1;
- }
- if (tl == l && tr == r) {
- return t[v];
- }
- long long tm = (tl + tr) / 2;
- long long fst = mx(a, t, 2 * v, tl, tm, l, min(tm, r));
- long long scd = mx(a, t, 2 * v+1, tm+1, tr, max(l, tm+1), r);
- if (a[fst] > a[scd]) {
- return fst;
- }
- else {
- return scd;
- }
- }
- int main() {
- long long n;
- cin >> n;
- vector<long long> a(n+1), t(4 * n), ans;
- for (long long i = 0; i < n; i++) {
- cin >> a[i];
- }
- a[n] = 0;
- build(a, t, 1, 0, n - 1);
- long long k = 0;
- cin >> k;
- for (int i = 0; i < k; i++) {
- long long l, r;
- cin >> l >> r;
- ans.push_back(mx(a, t, 1, 0, n - 1, l-1, r-1));
- }
- long long s = ans.size();
- /*for (long long i = 0; i < 4*n; i++) {
- cout << t[i] << " ";
- }
- cout << endl;*/
- for (long long i = 0; i < s; i++) {
- cout << ans[i]+1 << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement