4914 2023. 04. 06 23:21:57 TomaSajt Legmesszebbi rossz sorrendű (35 pont) cpp17 Elfogadva 35/35 64ms 10056 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct segtree {
  int size;
  vector<int> v;
  segtree(int size) : size(size), v(size * 4, INT_MAX) {}
  void set(int i, int val) { set(i, val, 0, 0, size); }

  void set(int i, int val, int x, int lx, int rx) {
    if (lx + 1 == rx) {
      v[x] = val;
      return;
    }
    int m = (lx + rx) / 2;
    if (i < m)
      set(i, val, 2 * x + 1, lx, m);
    else
      set(i, val, 2 * x + 2, m, rx);

    v[x] = min(v[2 * x + 1], v[2 * x + 2]);
  }

  int get(int l, int r) { return get(l, r, 0, 0, size); }
  int get(int l, int r, int x, int lx, int rx) {
    if (rx <= l || r <= lx)
      return INT_MAX;
    if (l <= lx && rx <= r)
      return v[x];
    int m = (lx + rx) / 2;
    return min(get(l, r, 2 * x + 1, lx, m), get(l, r, 2 * x + 2, m, rx));
  }
};

int main() {
  cin.tie(0), cin.sync_with_stdio(0);
  int n;
  cin >> n;
  segtree st(200001);

  int bestDist = -1;
  set<pair<int, int>> sols;

  for (int i = 0; i < n; i++) {
    int vi;
    cin >> vi;
    vi += 100000;
    int j = st.get(vi + 1, 200001);
    if (st.get(vi, vi + 1) == INT_MAX)
      st.set(vi, i);
    if (j == INT_MAX)
      continue;
    int dist = i - j + 1;
    if (dist >= bestDist) {
      if (dist != bestDist)
        sols.clear();
      bestDist = dist;
      sols.insert({j, i});
    }
  }
  if (sols.size() == 0) {
    cout << "-1";
    return 0;
  }
  cout << sols.begin()->first + 1 << ' ' << sols.begin()->second + 1;
  return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 35/35
1 Elfogadva 0/0 4ms 8116 KiB
2 Elfogadva 0/0 64ms 8372 KiB
3 Elfogadva 1/1 4ms 8292 KiB
4 Elfogadva 1/1 4ms 8296 KiB
5 Elfogadva 1/1 4ms 8548 KiB
6 Elfogadva 1/1 4ms 8764 KiB
7 Elfogadva 1/1 4ms 8976 KiB
8 Elfogadva 1/1 6ms 8928 KiB
9 Elfogadva 1/1 6ms 8948 KiB
10 Elfogadva 1/1 7ms 8948 KiB
11 Elfogadva 1/1 8ms 8948 KiB
12 Elfogadva 2/2 26ms 9228 KiB
13 Elfogadva 2/2 28ms 9188 KiB
14 Elfogadva 2/2 29ms 9144 KiB
15 Elfogadva 2/2 20ms 9288 KiB
16 Elfogadva 2/2 30ms 9396 KiB
17 Elfogadva 2/2 48ms 9632 KiB
18 Elfogadva 2/2 54ms 9760 KiB
19 Elfogadva 2/2 57ms 9716 KiB
20 Elfogadva 2/2 59ms 9716 KiB
21 Elfogadva 2/2 64ms 9844 KiB
22 Elfogadva 2/2 64ms 10036 KiB
23 Elfogadva 2/2 52ms 10056 KiB
24 Elfogadva 2/2 54ms 9988 KiB