oj.uz

Submission #959835

# Submission time Handle Problem Language Result Execution time Memory
959835 2024-04-09T07:38:36 Z kilkuwu Sequence (APIO23_sequence) C++17
11 / 100
 2000 ms 55128 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, {-1}); 
      }

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

      for (int i = 0; i + mid <= sz; i++) {
        int l = pos[v][i];
        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, r2 = rr.mx;

        if (std::max(l1, l2) <= std::min(r1, r2)) return true;
        int v = std::min(std::abs(r1 - l2), std::abs(r2 - l1));
        if (v <= mid) return true;
      }

      for (int i : pos[v]) {
        tree.update(i + 1, N, {-1}); // 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 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 10 ms 604 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 600 KB Output is correct
16 Correct 11 ms 604 KB Output is correct
17 Correct 10 ms 604 KB Output is correct
18 Correct 9 ms 648 KB Output is correct
19 Correct 9 ms 600 KB Output is correct
20 Correct 9 ms 604 KB Output is correct
21 Incorrect 10 ms 604 KB Output isn't correct
22 Halted 0 ms 0 KB -

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 2050 ms 49504 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 348 KB Output is correct
2 Execution timed out 2035 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 2055 ms 55128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 10 ms 604 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 600 KB Output is correct
16 Correct 11 ms 604 KB Output is correct
17 Correct 10 ms 604 KB Output is correct
18 Correct 9 ms 648 KB Output is correct
19 Correct 9 ms 600 KB Output is correct
20 Correct 9 ms 604 KB Output is correct
21 Incorrect 10 ms 604 KB Output isn't correct
22 Halted 0 ms 0 KB -

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 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 10 ms 604 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 600 KB Output is correct
16 Correct 11 ms 604 KB Output is correct
17 Correct 10 ms 604 KB Output is correct
18 Correct 9 ms 648 KB Output is correct
19 Correct 9 ms 600 KB Output is correct
20 Correct 9 ms 604 KB Output is correct
21 Incorrect 10 ms 604 KB Output isn't correct
22 Halted 0 ms 0 KB -