fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector<pair<int, int>> tree;
  5. pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
  6.     if (a.first > b.first) {
  7.         return a;
  8.     }
  9.     if (a.first < b.first) {
  10.         return b;
  11.     }
  12.     return {a.first, a.second<b.second};
  13. }
  14. void build(int a[], int v, int l, int r) {
  15.     if (r - l == 1) {
  16.         tree[v] = {a[l], l};
  17.         return;
  18.     }
  19.     int m = (l + r) / 2;
  20.     build(a, 2 * v + 1, l, m);
  21.     build(a, 2 * v + 2, m, r);
  22.     tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
  23. }
  24. pair<int, int> get(int v, int l, int r, int ql, int qr) {
  25.     if (ql >= r || qr <= l) {
  26.         return {0, -1};
  27.     }
  28.     if (ql <= l && qr >= r) {
  29.         return tree[v];
  30.     }
  31.     int m = (l + r) / 2;
  32.     return merge(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
  33. }
  34.  
  35. int main() {
  36.     int n;
  37.     cin >> n;
  38.     int a[n];
  39.     for (int i = 0; i < n; i++) {
  40.         cin >> a[i];
  41.     }
  42.  
  43.     tree.resize(4 * n);
  44.     build(a, 0, 0, n);
  45.  
  46.     int k;
  47.     cin >> k;
  48.  
  49.     while (k--) {
  50.         int l, r;
  51.         cin >> l >> r;
  52.         pair<int, int> res = get(0, 0, n, l - 1, r);
  53.         cout << res.second + 1 << " ";  
  54.     }
  55.  
  56.     cout << endl;
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
2 2 2 1 5
2
2 3
2 5
stdout
copy 
2 5
https://ideone.com/ajQomT
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!