oj.uz

Submission #959843

# Submission time Handle Problem Language Result Execution time Memory
959843 2024-04-09T08:07:36 Z kilkuwu Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 55232 KB 
#include "sequence.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/dbgnc.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct Tag {
  int add = 0;

  void apply(const Tag& t) {
    add += t.add;
  }
};

struct Info {
  int mn = 0, mx = 0;  

  void apply(const Tag& t) {
    mn += t.add, mx += t.add;
  }
};

Info operator+(const Info& a, const Info& b) {
  return {std::min(a.mn, b.mn), std::max(a.mx, b.mx)};
}

struct SegmentTree {
  int n;
  std::vector<Info> info;
  std::vector<Tag> tag;

  SegmentTree(int _n) : n(_n), info(4 * n), tag(4 * n) {}

  void apply(int k, const Tag& t) {
    info[k].apply(t);
    tag[k].apply(t);
  }
  
  void push(int k) {
    apply(k * 2, tag[k]);
    apply(k * 2 + 1, tag[k]);
    tag[k] = Tag();
  }

  void update(int k, int l, int r, int ql, int qr, const Tag& t) {
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
      info[k].apply(t);
      tag[k].apply(t);
      return;
    }

    push(k);

    int mid = (l + r) / 2;
    update(k * 2, l, mid, ql, qr, t);
    update(k * 2 + 1, mid + 1, r, ql, qr, t);
    info[k] = info[k * 2] + info[k * 2 + 1];
  }

  Info query(int k, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {(int) 1e9, (int) -1e9};
    if (ql <= l && r <= qr) {
      return info[k];
    }

    push(k);
    int mid = (l + r) / 2;
    return query(k * 2, l, mid, ql, qr) + query(k * 2 + 1, mid + 1, r, ql, qr);
  }

  void update(int l, int r, const Tag& t) {
    update(1, 0, n - 1, l, r, t);
  }

  Info query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }
};

int sequence(int N, std::vector<int> A) {
  std::vector<std::vector<int>> pos(N);

  for (int i = 0; i < N; i++) {
    pos[--A[i]].push_back(i);
  }

  auto check = [&](int mid) {
    SegmentTree tree(N + 1);

    for (int i = 0; i < N; i++) {
      tree.update(i + 1, N, {1});
    }

    for (int v = 0; v < N; v++) {
      for (int i : pos[v]) {
        tree.update(i + 1, N, {-2}); 
      }

      int sz = pos[v].size();

      for (int i = sz - 1; i >= 0; i--) {
        int l = pos[v][i];
        tree.update(l + 1, N, {2});
        if (i + mid <= sz) {
          int r = pos[v][i + mid - 1];
          auto rl = tree.query(0, l);
          int l1 = rl.mn, r1 = rl.mx;
          auto rr = tree.query(r + 1, N);
          int l2 = rr.mn - 2 * mid, r2 = rr.mx;

          if (std::max(l1, l2) <= std::min(r1, r2)) return true;
        }
      }

      for (int i : pos[v]) {
        tree.update(i + 1, N, {-2}); // becomes -1
      }
    }

    return false;
  };

  int lb = 1, rb = N;

  while (lb < rb) {
    int mid = (lb + rb + 1) / 2;

    if (check(mid)) {
      lb = mid;
    } else {
      rb = mid - 1;
    }
  }
  
  return lb;
}

#ifdef LOCAL
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}

#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 380 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 380 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 13 ms 604 KB Output is correct
14 Correct 13 ms 604 KB Output is correct
15 Correct 11 ms 604 KB Output is correct
16 Correct 16 ms 604 KB Output is correct
17 Correct 11 ms 604 KB Output is correct
18 Correct 11 ms 600 KB Output is correct
19 Correct 12 ms 856 KB Output is correct
20 Correct 12 ms 624 KB Output is correct
21 Correct 12 ms 600 KB Output is correct
22 Correct 12 ms 604 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 2045 ms 49748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 380 KB Output is correct
2 Execution timed out 2009 ms 41804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 55232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 380 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 13 ms 604 KB Output is correct
14 Correct 13 ms 604 KB Output is correct
15 Correct 11 ms 604 KB Output is correct
16 Correct 16 ms 604 KB Output is correct
17 Correct 11 ms 604 KB Output is correct
18 Correct 11 ms 600 KB Output is correct
19 Correct 12 ms 856 KB Output is correct
20 Correct 12 ms 624 KB Output is correct
21 Correct 12 ms 600 KB Output is correct
22 Correct 12 ms 604 KB Output is correct
23 Correct 1091 ms 8740 KB Output is correct
24 Correct 1145 ms 8748 KB Output is correct
25 Correct 1112 ms 8740 KB Output is correct
26 Correct 973 ms 7640 KB Output is correct
27 Correct 1053 ms 7652 KB Output is correct
28 Correct 997 ms 7644 KB Output is correct
29 Correct 872 ms 7260 KB Output is correct
30 Correct 926 ms 7404 KB Output is correct
31 Correct 798 ms 7472 KB Output is correct
32 Correct 1063 ms 9656 KB Output is correct
33 Correct 903 ms 8536 KB Output is correct
34 Correct 1025 ms 8564 KB Output is correct
35 Correct 1006 ms 8508 KB Output is correct
36 Correct 1020 ms 8608 KB Output is correct
37 Correct 1022 ms 8784 KB Output is correct
38 Correct 1097 ms 8636 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 380 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 13 ms 604 KB Output is correct
14 Correct 13 ms 604 KB Output is correct
15 Correct 11 ms 604 KB Output is correct
16 Correct 16 ms 604 KB Output is correct
17 Correct 11 ms 604 KB Output is correct
18 Correct 11 ms 600 KB Output is correct
19 Correct 12 ms 856 KB Output is correct
20 Correct 12 ms 624 KB Output is correct
21 Correct 12 ms 600 KB Output is correct
22 Correct 12 ms 604 KB Output is correct
23 Execution timed out 2045 ms 49748 KB Time limit exceeded
24 Halted 0 ms 0 KB -