oj.uz

Submission #848624

# Submission time Handle Problem Language Result Execution time Memory
848624 2023-09-13T06:08:54 Z hntvnoi Sequence (APIO23_sequence) C++17
69 / 100
 2000 ms 61352 KB 
#include<bits/stdc++.h>
#include "sequence.h"
using namespace std;
 
#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << x)
#define db(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
constexpr int INF = 0x3f3f3f3f;
 
#define N 500005
 
int n;
int a[N], min_i[N], max_i[N], max_j[N], min_j[N];
vector<int> pos[N];
 
template<class T>
  inline T pullmax(T a, T b) {
    return max(a, b);
  }
 
template<class T>
  inline T pullmin(T a, T b) {
    return min(a, b);
  }
 
template<class T>
  inline void maxi(T &a, T b) {
    if (a < b) a = b;
  }
 
template<class T>
  inline void add(T &a, T b) {
    a += b;
  }
  
template<class T>
  struct Segtree {
    int n; vector<T> s, lazy;
    Segtree(int n = 0): n(n) {
      s.resize(4 << __lg(n + 1));
      lazy.resize(4 << __lg(n + 1));
    }
    void propagate(int id, void add(T &a, T b)) {
      T &t = lazy[id];
      if (!t) return;
      add(s[id << 1], t);
      add(s[id << 1 | 1], t);
      add(lazy[id << 1], t);
      add(lazy[id << 1 | 1], t);
      t = 0;
    }
    void update(int id, int l, int r, int u, int v, T val, T pull(T a, T b), void add(T &a, T b)) {
      if (u <= l && r <= v) {
        add(s[id], val);
        if (l != r) add(lazy[id], val);
        return;
      }
      propagate(id, add);
      int mid = (l + r) >> 1;
      if (u <= mid && mid < v) {
        update(id << 1, l, mid, u, v, val, pull, add);
        update(id << 1 | 1, mid + 1, r, u, v, val, pull, add);
      } else if (mid < u) {
        update(id << 1 | 1, mid + 1, r, u, v, val, pull, add);
      } else update(id << 1, l, mid, u, v, val, pull, add);
      s[id] = pull(s[id << 1], s[id << 1 | 1]);
    }
    void update(int l, int r, T val, T pull(T a, T b), void add(T &a, T b)) {
      update(1, 0, n, l, r, val, pull, add);
    }
    T get(int id, int l, int r, int u, int v, T pull(T a, T b), void add(T &a, T b)) {
      if (u <= l && r <= v) return s[id];
      propagate(id, add);
      int mid = (l + r) >> 1;
      if (u <= mid && mid < v) return pull(get(id << 1, l, mid, u, v, pull, add), get(id << 1 | 1, mid + 1, r, u, v, pull, add));
      if (mid < u) return get(id << 1 | 1, mid + 1, r, u, v, pull, add);
      return get(id << 1, l, mid, u, v, pull, add);
    }
    T get(int u, int v, T pull(T a, T b), void add(T &a, T b)) {
      u = max(0, u), v = max(0, v);
      if (u > v) return INF;
      return get(1, 0, n, u, v, pull, add);
    }
  };
 
int sequence(int n, vector<int> values) {
  for (int i = 1; i <= n; ++i) {
    a[i] = values[i - 1];
    pos[a[i]].emplace_back(i);
  }
  sort(values.begin(), values.end());
  values.erase(unique(values.begin(), values.end()), values.end());
  reverse(values.begin(), values.end());
  Segtree<int> stmax(n + 1), stmin(n + 1);
  int res = 0;
  auto solve = [&](int x) {
    pos[x].emplace_back(0);
    sort(pos[x].begin(), pos[x].end());
    vector<int> vals;
    for (int i = 0; i < int(pos[x].size()); ++i) {
      int L = pos[x][i], R = n + 1;
      bool okay = 0;
      if (i < int(pos[x].size()) - 1) R = pos[x][i + 1], okay = 1;
      min_i[i] = stmin.get(L, R - 1, pullmin, add);
      max_i[i] = stmax.get(L, R - 1, pullmax, add);
      max_j[i] = stmax.get(L, R - 1, pullmax, add);
      min_j[i] = stmin.get(L, R - 1, pullmin, add);
      vals.emplace_back(min_j[i] - 2 * i);
      vals.emplace_back(max_j[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    vector<int> ordmin_i(pos[x].size()), ordmax_j(pos[x].size());
    iota(ordmin_i.begin(), ordmin_i.end(), 0);
    iota(ordmax_j.begin(), ordmax_j.end(), 0);
    sort(ordmin_i.begin(), ordmin_i.end(), [&](int i, int j) {
      return min_i[i] > min_i[j];
    });
    sort(ordmax_j.begin(), ordmax_j.end(), [&](int i, int j) {
      return max_j[i] > max_j[j];
    });
    auto ID = [&](int val) {
      return lower_bound(vals.begin(), vals.end(), val) - vals.begin() + 1;
    };
    auto IDR = [&](int val) {
      return upper_bound(vals.begin(), vals.end(), val) - vals.begin();
    };
    Segtree<int> stpos(vals.size());
    int j = 0;
    for (int i = 0; i < int(pos[x].size()); ++i) {
      int val = ordmin_i[i];
      while (j < int(pos[x].size()) && max_j[ordmax_j[j]] >= min_i[val]) {
        int pos = ordmax_j[j++];
        if (min_j[pos] != INF) {
          int l = ID(min_j[pos] - 2 * pos), r = ID(max_j[pos]);
          stpos.update(l, r, pos, pullmax, maxi);
        }
      }
      if (min_i[val] != INF) {
        int l = ID(min_i[val] - 2 * val), r = IDR(max_i[val] - 2 * val);
        int id = stpos.get(l, r, pullmax, maxi);
        if (id != INF) res = max(res, id - val);
      }
    }
  };
  for (int i = 0; i < int(values.size()); ++i) {
    int x = values[i];
    if (i == 0) {
      vector<int> pref(n + 1);
      for (int j = 1; j <= n; ++j) pref[j] = pref[j - 1] + (a[j] >= x ? 1 : -1);
      for (int j = 0; j <= n; ++j) {
        stmax.update(j, j, pref[j], pullmax, add);
        stmin.update(j, j, pref[j], pullmin, add);
      }
    } else for (int id : pos[x]) {
      stmax.update(id, n, 2, pullmax, add);
      stmin.update(id, n, 2, pullmin, add);
    }
    solve(x);
  }
  return res;
}

Compilation message

sequence.cpp: In lambda function:
sequence.cpp:103:12: warning: variable 'okay' set but not used [-Wunused-but-set-variable]
  103 |       bool okay = 0;
      |            ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21080 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21080 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 8 ms 21252 KB Output is correct
14 Correct 8 ms 21072 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21232 KB Output is correct
17 Correct 7 ms 21236 KB Output is correct
18 Correct 8 ms 21276 KB Output is correct
19 Correct 8 ms 21080 KB Output is correct
20 Correct 9 ms 21340 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 9 ms 21256 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 1464 ms 55880 KB Output is correct
3 Correct 1484 ms 55724 KB Output is correct
4 Correct 1148 ms 51364 KB Output is correct
5 Correct 1480 ms 55292 KB Output is correct
6 Correct 1420 ms 55308 KB Output is correct
7 Correct 1212 ms 46800 KB Output is correct
8 Correct 1191 ms 46948 KB Output is correct
9 Correct 1307 ms 56860 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 1247 ms 59996 KB Output is correct
3 Correct 1152 ms 52588 KB Output is correct
4 Correct 1118 ms 52976 KB Output is correct
5 Correct 1057 ms 59732 KB Output is correct
6 Correct 952 ms 53724 KB Output is correct

Subtask #5
0.0 / 13.0

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

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21080 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 8 ms 21252 KB Output is correct
14 Correct 8 ms 21072 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21232 KB Output is correct
17 Correct 7 ms 21236 KB Output is correct
18 Correct 8 ms 21276 KB Output is correct
19 Correct 8 ms 21080 KB Output is correct
20 Correct 9 ms 21340 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 9 ms 21256 KB Output is correct
23 Correct 267 ms 27924 KB Output is correct
24 Correct 265 ms 27916 KB Output is correct
25 Correct 293 ms 27928 KB Output is correct
26 Correct 205 ms 26756 KB Output is correct
27 Correct 215 ms 26836 KB Output is correct
28 Correct 207 ms 26836 KB Output is correct
29 Correct 183 ms 27168 KB Output is correct
30 Correct 190 ms 27208 KB Output is correct
31 Correct 118 ms 32016 KB Output is correct
32 Correct 229 ms 28816 KB Output is correct
33 Correct 271 ms 27980 KB Output is correct
34 Correct 263 ms 27924 KB Output is correct
35 Correct 267 ms 28180 KB Output is correct
36 Correct 249 ms 28436 KB Output is correct
37 Correct 260 ms 28180 KB Output is correct
38 Correct 255 ms 28216 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21080 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 8 ms 21252 KB Output is correct
14 Correct 8 ms 21072 KB Output is correct
15 Correct 7 ms 21084 KB Output is correct
16 Correct 7 ms 21232 KB Output is correct
17 Correct 7 ms 21236 KB Output is correct
18 Correct 8 ms 21276 KB Output is correct
19 Correct 8 ms 21080 KB Output is correct
20 Correct 9 ms 21340 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 9 ms 21256 KB Output is correct
23 Correct 1464 ms 55880 KB Output is correct
24 Correct 1484 ms 55724 KB Output is correct
25 Correct 1148 ms 51364 KB Output is correct
26 Correct 1480 ms 55292 KB Output is correct
27 Correct 1420 ms 55308 KB Output is correct
28 Correct 1212 ms 46800 KB Output is correct
29 Correct 1191 ms 46948 KB Output is correct
30 Correct 1307 ms 56860 KB Output is correct
31 Correct 1247 ms 59996 KB Output is correct
32 Correct 1152 ms 52588 KB Output is correct
33 Correct 1118 ms 52976 KB Output is correct
34 Correct 1057 ms 59732 KB Output is correct
35 Correct 952 ms 53724 KB Output is correct
36 Execution timed out 2021 ms 61352 KB Time limit exceeded
37 Halted 0 ms 0 KB -