oj.uz

Submission #885118

# Submission time Handle Problem Language Result Execution time Memory
885118 2023-12-09T03:02:01 Z fanwen Sequence (APIO23_sequence) C++17
100 / 100
 1070 ms 170404 KB 
#include <bits/stdc++.h>

#define fi first 
#define se second 

using namespace std;

const int MAX = 5e5 + 5;

int A[MAX];
vector <int> pos[MAX], max_pref[MAX], min_pref[MAX], max_suff[MAX], min_suff[MAX];

struct node {
  int ma, mi, lazy;
  node(int ma = 0, int mi = 0) : ma(ma), mi(mi), lazy(0) {}
} it[MAX << 2];

node merge(const node &a, const node &b) {
  return node(max(a.ma, b.ma), min(a.mi, b.mi));
}

void build(int idx, int l, int r) {
  if(l == r) it[idx] = node(l, r);
  else {
    int mid = l + r >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
  }
}

void push(int idx) {
  if(!it[idx].lazy) return;
  it[idx << 1].ma += it[idx].lazy;
  it[idx << 1].mi += it[idx].lazy;
  it[idx << 1 | 1].ma += it[idx].lazy;
  it[idx << 1 | 1].mi += it[idx].lazy;
  it[idx << 1].lazy += it[idx].lazy;
  it[idx << 1 | 1].lazy += it[idx].lazy;
  it[idx].lazy = 0;
}

void update(int idx, int l, int r, int u, int v, int val) {
  if(l > v || r < u) return;
  if(l >= u && r <= v) {
    it[idx].ma += val;
    it[idx].mi += val;
    it[idx].lazy += val;
    return;
  }

  push(idx);

  int mid = l + r >> 1;

  update(idx << 1, l, mid, u, v, val);
  update(idx << 1 | 1, mid + 1, r, u, v, val);

  it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}

node get(int idx, int l, int r, int u, int v) {
  if(l > v || r < u) return node(-1e9, 1e9);
  if(l >= u && r <= v) return it[idx];

  push(idx);

  int mid = l + r >> 1;

  return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}

int sequence(int n, vector <int> a) {
  for (int i = 0; i < n; ++i) A[i + 1] = a[i];
  for (int i = 1; i <= n; ++i) pos[A[i]].push_back(i);
  // for (int i = 1; i <= n; ++i) cout << A[i] << " \n"[i == n];
  build(1, 0, n);
  for (int i = 1; i <= n; ++i) {
    for (auto &j : pos[i]) {
      min_pref[i].push_back(get(1, 0, n, 0, j - 1).mi);
      max_suff[i].push_back(get(1, 0, n, j, n).ma);
    }

    for (auto &j : pos[i]) update(1, 0, n, j, n, -2);

    for (auto &j : pos[i]) {
      min_suff[i].push_back(get(1, 0, n, j, n).mi);
      max_pref[i].push_back(get(1, 0, n, 0, j - 1).ma);
    }
  }
  auto check = [&] (int res) -> bool {
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j + res - 1 < (int) pos[i].size(); ++j) {
        if(max_pref[i][j] >= min_suff[i][j + res - 1] && max_suff[i][j + res - 1] >= min_pref[i][j]) {
          return true;
        }
      }
    }
    return false;
  };

  int l = -1, r = n + 1;
  // for (auto x : max_pref[1]) cout << x << " "; cout << '\n';
  // for (auto x : min_pref[1]) cout << x << " "; cout << '\n';
  // for (auto x : max_suff[1]) cout << x << " "; cout << '\n';
  // for (auto x : min_suff[1]) cout << x << " "; cout << '\n';
  // cout << check(3) << '\n';
  while(r - l > 1) {
    int mid = l + r >> 1;
    // cout << mid << endl;
    if(check(mid)) l = mid;
    else r = mid;
  }
  return l;
}

#ifdef local 

signed main() {
  freopen("TASK.inp", "r", stdin);
  freopen("TASK.out", "w", stdout);

  int n; cin >> n; vector <int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  cout << sequence(n, a); 
}

#endif // local

Compilation message

sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:109:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 17 ms 82524 KB Output is correct
4 Correct 18 ms 82968 KB Output is correct
5 Correct 18 ms 82700 KB Output is correct
6 Correct 18 ms 82524 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 18 ms 82524 KB Output is correct
9 Correct 19 ms 82676 KB Output is correct
10 Correct 18 ms 82656 KB Output is correct
11 Correct 18 ms 82520 KB Output is correct
12 Correct 17 ms 82520 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 17 ms 82524 KB Output is correct
4 Correct 18 ms 82968 KB Output is correct
5 Correct 18 ms 82700 KB Output is correct
6 Correct 18 ms 82524 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 18 ms 82524 KB Output is correct
9 Correct 19 ms 82676 KB Output is correct
10 Correct 18 ms 82656 KB Output is correct
11 Correct 18 ms 82520 KB Output is correct
12 Correct 17 ms 82520 KB Output is correct
13 Correct 20 ms 82776 KB Output is correct
14 Correct 20 ms 82776 KB Output is correct
15 Correct 19 ms 82716 KB Output is correct
16 Correct 19 ms 82520 KB Output is correct
17 Correct 20 ms 82768 KB Output is correct
18 Correct 19 ms 82780 KB Output is correct
19 Correct 19 ms 82656 KB Output is correct
20 Correct 20 ms 82776 KB Output is correct
21 Correct 20 ms 82780 KB Output is correct
22 Correct 20 ms 82776 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 812 ms 138032 KB Output is correct
3 Correct 810 ms 141348 KB Output is correct
4 Correct 678 ms 100828 KB Output is correct
5 Correct 818 ms 136408 KB Output is correct
6 Correct 799 ms 136652 KB Output is correct
7 Correct 697 ms 101328 KB Output is correct
8 Correct 687 ms 101460 KB Output is correct
9 Correct 685 ms 99752 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82524 KB Output is correct
2 Correct 702 ms 99684 KB Output is correct
3 Correct 693 ms 100220 KB Output is correct
4 Correct 694 ms 100192 KB Output is correct
5 Correct 695 ms 103636 KB Output is correct
6 Correct 697 ms 99640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 166520 KB Output is correct
2 Correct 966 ms 169912 KB Output is correct
3 Correct 979 ms 167292 KB Output is correct
4 Correct 971 ms 166932 KB Output is correct
5 Correct 872 ms 150352 KB Output is correct
6 Correct 861 ms 150168 KB Output is correct
7 Correct 760 ms 144212 KB Output is correct
8 Correct 764 ms 142684 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 17 ms 82524 KB Output is correct
4 Correct 18 ms 82968 KB Output is correct
5 Correct 18 ms 82700 KB Output is correct
6 Correct 18 ms 82524 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 18 ms 82524 KB Output is correct
9 Correct 19 ms 82676 KB Output is correct
10 Correct 18 ms 82656 KB Output is correct
11 Correct 18 ms 82520 KB Output is correct
12 Correct 17 ms 82520 KB Output is correct
13 Correct 20 ms 82776 KB Output is correct
14 Correct 20 ms 82776 KB Output is correct
15 Correct 19 ms 82716 KB Output is correct
16 Correct 19 ms 82520 KB Output is correct
17 Correct 20 ms 82768 KB Output is correct
18 Correct 19 ms 82780 KB Output is correct
19 Correct 19 ms 82656 KB Output is correct
20 Correct 20 ms 82776 KB Output is correct
21 Correct 20 ms 82780 KB Output is correct
22 Correct 20 ms 82776 KB Output is correct
23 Correct 154 ms 91260 KB Output is correct
24 Correct 149 ms 91380 KB Output is correct
25 Correct 153 ms 91476 KB Output is correct
26 Correct 132 ms 86516 KB Output is correct
27 Correct 130 ms 86356 KB Output is correct
28 Correct 126 ms 86352 KB Output is correct
29 Correct 112 ms 85148 KB Output is correct
30 Correct 115 ms 85076 KB Output is correct
31 Correct 111 ms 85708 KB Output is correct
32 Correct 128 ms 95972 KB Output is correct
33 Correct 149 ms 90456 KB Output is correct
34 Correct 149 ms 90600 KB Output is correct
35 Correct 146 ms 90164 KB Output is correct
36 Correct 148 ms 90208 KB Output is correct
37 Correct 146 ms 90196 KB Output is correct
38 Correct 145 ms 90412 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 17 ms 82524 KB Output is correct
4 Correct 18 ms 82968 KB Output is correct
5 Correct 18 ms 82700 KB Output is correct
6 Correct 18 ms 82524 KB Output is correct
7 Correct 17 ms 82524 KB Output is correct
8 Correct 18 ms 82524 KB Output is correct
9 Correct 19 ms 82676 KB Output is correct
10 Correct 18 ms 82656 KB Output is correct
11 Correct 18 ms 82520 KB Output is correct
12 Correct 17 ms 82520 KB Output is correct
13 Correct 20 ms 82776 KB Output is correct
14 Correct 20 ms 82776 KB Output is correct
15 Correct 19 ms 82716 KB Output is correct
16 Correct 19 ms 82520 KB Output is correct
17 Correct 20 ms 82768 KB Output is correct
18 Correct 19 ms 82780 KB Output is correct
19 Correct 19 ms 82656 KB Output is correct
20 Correct 20 ms 82776 KB Output is correct
21 Correct 20 ms 82780 KB Output is correct
22 Correct 20 ms 82776 KB Output is correct
23 Correct 812 ms 138032 KB Output is correct
24 Correct 810 ms 141348 KB Output is correct
25 Correct 678 ms 100828 KB Output is correct
26 Correct 818 ms 136408 KB Output is correct
27 Correct 799 ms 136652 KB Output is correct
28 Correct 697 ms 101328 KB Output is correct
29 Correct 687 ms 101460 KB Output is correct
30 Correct 685 ms 99752 KB Output is correct
31 Correct 702 ms 99684 KB Output is correct
32 Correct 693 ms 100220 KB Output is correct
33 Correct 694 ms 100192 KB Output is correct
34 Correct 695 ms 103636 KB Output is correct
35 Correct 697 ms 99640 KB Output is correct
36 Correct 992 ms 166520 KB Output is correct
37 Correct 966 ms 169912 KB Output is correct
38 Correct 979 ms 167292 KB Output is correct
39 Correct 971 ms 166932 KB Output is correct
40 Correct 872 ms 150352 KB Output is correct
41 Correct 861 ms 150168 KB Output is correct
42 Correct 760 ms 144212 KB Output is correct
43 Correct 764 ms 142684 KB Output is correct
44 Correct 154 ms 91260 KB Output is correct
45 Correct 149 ms 91380 KB Output is correct
46 Correct 153 ms 91476 KB Output is correct
47 Correct 132 ms 86516 KB Output is correct
48 Correct 130 ms 86356 KB Output is correct
49 Correct 126 ms 86352 KB Output is correct
50 Correct 112 ms 85148 KB Output is correct
51 Correct 115 ms 85076 KB Output is correct
52 Correct 111 ms 85708 KB Output is correct
53 Correct 128 ms 95972 KB Output is correct
54 Correct 149 ms 90456 KB Output is correct
55 Correct 149 ms 90600 KB Output is correct
56 Correct 146 ms 90164 KB Output is correct
57 Correct 148 ms 90208 KB Output is correct
58 Correct 146 ms 90196 KB Output is correct
59 Correct 145 ms 90412 KB Output is correct
60 Correct 1033 ms 141784 KB Output is correct
61 Correct 1070 ms 141380 KB Output is correct
62 Correct 1041 ms 141368 KB Output is correct
63 Correct 818 ms 104724 KB Output is correct
64 Correct 816 ms 104724 KB Output is correct
65 Correct 841 ms 104788 KB Output is correct
66 Correct 701 ms 100764 KB Output is correct
67 Correct 705 ms 100716 KB Output is correct
68 Correct 690 ms 103108 KB Output is correct
69 Correct 783 ms 170404 KB Output is correct
70 Correct 984 ms 136732 KB Output is correct
71 Correct 999 ms 136264 KB Output is correct
72 Correct 975 ms 133984 KB Output is correct
73 Correct 1016 ms 135372 KB Output is correct
74 Correct 986 ms 133484 KB Output is correct
75 Correct 1000 ms 135620 KB Output is correct