oj.uz

Submission #884068

# Submission time Handle Problem Language Result Execution time Memory
884068 2023-12-06T15:24:06 Z nguyentunglam Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 54440 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;

vector<int> pos[N];

int L[N], R[N];

int minx[N << 2], maxx[N << 2], lazy[N << 2];

void push(int s, int l, int r) {
  if (!lazy[s]) return;
  minx[s] += lazy[s];
  maxx[s] += lazy[s];
  if (l != r) {
    lazy[s << 1] += lazy[s];
    lazy[s << 1 | 1] += lazy[s];
  }
  lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    lazy[s] = val;
    push(s, l, r);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
  minx[s] = min(minx[s << 1], minx[s << 1 | 1]);
  maxx[s] = max(maxx[s << 1], maxx[s << 1 | 1]);
}

int get_min(int s, int l, int r, int from, int to) {
  push(s, l, r);
  if (l > to || r < from) return 1e9;
  if (from <= l && r <= to) return minx[s];
  int mid = l + r >> 1;
  return min(get_min(s << 1, l, mid, from, to), get_min(s << 1 | 1, mid + 1, r, from, to));
}
int get_max(int s, int l, int r, int from, int to) {
  push(s, l, r);
  if (l > to || r < from) return -1e9;
  if (from <= l && r <= to) return maxx[s];
  int mid = l + r >> 1;
  return max(get_max(s << 1, l, mid, from, to), get_max(s << 1 | 1, mid + 1, r, from, to));
}

int sequence(int n, vector<int> a) {
    int ans = 1;

    a.insert(a.begin(), 0);

    for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);

    for(int i = 1; i <= n; i++) up(1, 0, n, i, i, -i);

    for(int val = 1; val <= n; val++) {
      pos[val].push_back(n + 1);
      int pre = 0;
      for(int i = 0; i + 1 < pos[val].size(); i++) {
        int cur = pos[val][i];
        L[i] = get_min(1, 0, n, 0, cur - 1);
        R[i] = get_max(1, 0, n, 0, cur - 1);
        int from = get_min(1, 0, n, cur, n);
        int to = get_max(1, 0, n, cur, n);
        for(int j = i - 1; j >= 0; j--) {
          if (max(L[j], from) <= min( R[j], to)) ans = max(ans, i - j + 1);
          else if (L[j] > to && to - L[j] + (i - j + 1) * 2 >= 0) ans = max(ans, i - j + 1);
        }
      }
      for(int &j : pos[val]) up(1, 0, n, j, n, 2);
    }
    return ans;
}

#ifdef ngu
int 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);

//    cout << sequence(7, {1, 2, 3, 1, 2, 1, 3});
//    cout << sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});
    cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});

}
#endif // ngu

Compilation message

sequence.cpp: In function 'void up(int, int, int, int, int, int)':
sequence.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int get_min(int, int, int, int, int)':
sequence.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int get_max(int, int, int, int, int)':
sequence.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:68:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |       for(int i = 0; i + 1 < pos[val].size(); i++) {
      |                      ~~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:67:11: warning: unused variable 'pre' [-Wunused-variable]
   67 |       int pre = 0;
      |           ^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20912 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 8 ms 20828 KB Output is correct
14 Correct 6 ms 21032 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 21044 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 6 ms 21000 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 21012 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 670 ms 52868 KB Output is correct
3 Correct 689 ms 53688 KB Output is correct
4 Execution timed out 2073 ms 39084 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20912 KB Output is correct
2 Execution timed out 2037 ms 41388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 53424 KB Output is correct
2 Correct 829 ms 53120 KB Output is correct
3 Correct 811 ms 53676 KB Output is correct
4 Correct 790 ms 54440 KB Output is correct
5 Correct 731 ms 54432 KB Output is correct
6 Correct 731 ms 53812 KB Output is correct
7 Correct 677 ms 54200 KB Output is correct
8 Correct 661 ms 53100 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20912 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 8 ms 20828 KB Output is correct
14 Correct 6 ms 21032 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 21044 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 6 ms 21000 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 21012 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 123 ms 29112 KB Output is correct
24 Correct 122 ms 29028 KB Output is correct
25 Correct 128 ms 28984 KB Output is correct
26 Correct 123 ms 29720 KB Output is correct
27 Correct 123 ms 29660 KB Output is correct
28 Correct 123 ms 29716 KB Output is correct
29 Correct 897 ms 29452 KB Output is correct
30 Correct 893 ms 29512 KB Output is correct
31 Execution timed out 2023 ms 28224 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20912 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 8 ms 20828 KB Output is correct
14 Correct 6 ms 21032 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 21044 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 6 ms 21000 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 21012 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 670 ms 52868 KB Output is correct
24 Correct 689 ms 53688 KB Output is correct
25 Execution timed out 2073 ms 39084 KB Time limit exceeded
26 Halted 0 ms 0 KB -