57232023-09-10 01:32:49TomaSajtLegmesszebbi rossz sorrendű (35 pont)cpp17Elfogadva 35/3590ms30180 KiB
#include <bits/stdc++.h>
using namespace std;

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); // only set if this was the first occurance of vi

    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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base35/35
1Elfogadva0/03ms2048 KiB
2Elfogadva0/090ms21560 KiB
3Elfogadva1/13ms2992 KiB
4Elfogadva1/13ms3208 KiB
5Elfogadva1/13ms3428 KiB
6Elfogadva1/13ms3640 KiB
7Elfogadva1/13ms4020 KiB
8Elfogadva1/14ms4804 KiB
9Elfogadva1/14ms5752 KiB
10Elfogadva1/16ms6464 KiB
11Elfogadva1/18ms8620 KiB
12Elfogadva2/229ms12000 KiB
13Elfogadva2/234ms13516 KiB
14Elfogadva2/235ms14304 KiB
15Elfogadva2/223ms11224 KiB
16Elfogadva2/237ms15116 KiB
17Elfogadva2/264ms19960 KiB
18Elfogadva2/272ms22188 KiB
19Elfogadva2/279ms24436 KiB
20Elfogadva2/281ms25480 KiB
21Elfogadva2/289ms27732 KiB
22Elfogadva2/290ms28620 KiB
23Elfogadva2/268ms29312 KiB
24Elfogadva2/268ms30180 KiB