4918 2023. 04. 07 01:03:39 TomaSajt Legmesszebbi rossz sorrendű (35 pont) cpp17 Elfogadva 35/35 86ms 23676 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct seg_tree {
  int val{INT_MAX};
  seg_tree *lc{}, *rc{};
  int lx, rx;
  seg_tree(int lx, int rx) : lx{lx}, rx{rx} {}

  void ensure_children_exist() {
    int m = (lx + rx) / 2;
    if (!lc)
      lc = new seg_tree(lx, m);
    if (!rc)
      rc = new seg_tree(m, rx);
  }
  int get(int l, int r) {
    if (rx <= l || r <= lx)
      return INT_MAX;
    if (l <= lx && rx <= r)
      return val;
    ensure_children_exist();
    return min(lc->get(l, r), rc->get(l, r));
  }
  void set(int i, int v) {
    if (lx + 1 == rx) {
      val = v;
      return;
    }
    ensure_children_exist();
    if (i < lc->rx)
      lc->set(i, v);
    else
      rc->set(i, v);
    val = min(lc->val, rc->val);
  }
};

int main() {
  cin.tie(0), cin.sync_with_stdio(0);
  int n;
  cin >> n;
  seg_tree st(-100000, 100001);
  int bestI = -1, bestJ = 0;
  for (int i = 0; i < n; i++) {
    int vi;
    cin >> vi;
    int j = st.get(vi + 1, 100001);
    if (st.get(vi, vi + 1) == INT_MAX)
      st.set(vi, i);
    if (j == INT_MAX)
      continue;
    int d = i - j;
    int bestD = bestI - bestJ;
    if (d > bestD || (d == bestD && j < bestJ)) {
      bestI = i, bestJ = j;
    }
  }
  if (bestI == -1) {
    cout << "-1";
    return 0;
  }
  cout << bestJ + 1 << ' ' << bestI + 1;
  return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 35/35
1 Elfogadva 0/0 3ms 1896 KiB
2 Elfogadva 0/0 86ms 20716 KiB
3 Elfogadva 1/1 3ms 2372 KiB
4 Elfogadva 1/1 2ms 2396 KiB
5 Elfogadva 1/1 3ms 2528 KiB
6 Elfogadva 1/1 3ms 2864 KiB
7 Elfogadva 1/1 3ms 3164 KiB
8 Elfogadva 1/1 4ms 3624 KiB
9 Elfogadva 1/1 4ms 4604 KiB
10 Elfogadva 1/1 6ms 5688 KiB
11 Elfogadva 1/1 8ms 7492 KiB
12 Elfogadva 2/2 28ms 10960 KiB
13 Elfogadva 2/2 32ms 11888 KiB
14 Elfogadva 2/2 34ms 12500 KiB
15 Elfogadva 2/2 21ms 9424 KiB
16 Elfogadva 2/2 35ms 13236 KiB
17 Elfogadva 2/2 61ms 17784 KiB
18 Elfogadva 2/2 68ms 19416 KiB
19 Elfogadva 2/2 76ms 20940 KiB
20 Elfogadva 2/2 79ms 21464 KiB
21 Elfogadva 2/2 85ms 23196 KiB
22 Elfogadva 2/2 85ms 23376 KiB
23 Elfogadva 2/2 65ms 23436 KiB
24 Elfogadva 2/2 65ms 23676 KiB