oj.uz

Submission #959829

# Submission time Handle Problem Language Result Execution time Memory
959829 2024-04-09T07:30:58 Z kilkuwu Sequence (APIO23_sequence) C++17
11 / 100
 2000 ms 58448 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);

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

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

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 10 ms 600 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 616 KB Output is correct
16 Correct 9 ms 620 KB Output is correct
17 Correct 9 ms 612 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 600 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 1 ms 344 KB Output is correct
2 Execution timed out 2062 ms 52820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2031 ms 42788 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 2015 ms 58448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 10 ms 600 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 616 KB Output is correct
16 Correct 9 ms 620 KB Output is correct
17 Correct 9 ms 612 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 600 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 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 10 ms 600 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 616 KB Output is correct
16 Correct 9 ms 620 KB Output is correct
17 Correct 9 ms 612 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 600 KB Output is correct
21 Incorrect 10 ms 604 KB Output isn't correct
22 Halted 0 ms 0 KB -