49182023-04-07 01:03:39TomaSajtLegmesszebbi rossz sorrendű (35 pont)cpp17Elfogadva 35/3586ms23676 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ÖsszpontTesztVerdiktIdőMemória
base35/35
1Elfogadva0/03ms1896 KiB
2Elfogadva0/086ms20716 KiB
3Elfogadva1/13ms2372 KiB
4Elfogadva1/12ms2396 KiB
5Elfogadva1/13ms2528 KiB
6Elfogadva1/13ms2864 KiB
7Elfogadva1/13ms3164 KiB
8Elfogadva1/14ms3624 KiB
9Elfogadva1/14ms4604 KiB
10Elfogadva1/16ms5688 KiB
11Elfogadva1/18ms7492 KiB
12Elfogadva2/228ms10960 KiB
13Elfogadva2/232ms11888 KiB
14Elfogadva2/234ms12500 KiB
15Elfogadva2/221ms9424 KiB
16Elfogadva2/235ms13236 KiB
17Elfogadva2/261ms17784 KiB
18Elfogadva2/268ms19416 KiB
19Elfogadva2/276ms20940 KiB
20Elfogadva2/279ms21464 KiB
21Elfogadva2/285ms23196 KiB
22Elfogadva2/285ms23376 KiB
23Elfogadva2/265ms23436 KiB
24Elfogadva2/265ms23676 KiB