oj.uz

Submission #884056

# Submission time Handle Problem Language Result Execution time Memory
884056 2023-12-06T15:12:00 Z nguyentunglam Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 57628 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, pre, cur - 1);
        R[i] = get_max(1, 0, n, pre, cur - 1);
        int from = get_min(1, 0, n, cur, pos[val][i + 1] - 1);
        int to = get_max(1, 0, n, cur, pos[val][i + 1] - 1);
//        cout << cur << " " << pos[val][i + 1] - 1 << endl;
        for(int j = i - 1; j >= 0; j--) {
//          cout << L[j] << " " << R[j] << " " << from << " " << to << " " << j << " " << i << " " << to - L[j] + (i - j + 1) * 2 << endl;
//          cout << (L[j] > to && to - L[j] + (i - j + 1) * 2 >= 0) << endl;
          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++) {
      |                      ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 5 ms 20920 KB Output is correct
5 Correct 4 ms 20944 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20824 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 5 ms 20828 KB Output is correct
10 Correct 5 ms 20828 KB Output is correct
11 Correct 5 ms 20920 KB Output is correct
12 Correct 4 ms 20824 KB Output is correct
13 Correct 7 ms 20824 KB Output is correct
14 Correct 9 ms 21048 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 20828 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 7 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20968 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 20824 KB Output is correct
2 Correct 699 ms 57104 KB Output is correct
3 Correct 719 ms 57264 KB Output is correct
4 Execution timed out 2036 ms 41132 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 20828 KB Output is correct
2 Execution timed out 2079 ms 43692 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 56504 KB Output is correct
2 Correct 837 ms 56356 KB Output is correct
3 Correct 838 ms 57544 KB Output is correct
4 Correct 858 ms 57264 KB Output is correct
5 Correct 797 ms 57628 KB Output is correct
6 Correct 785 ms 55940 KB Output is correct
7 Correct 770 ms 56084 KB Output is correct
8 Correct 766 ms 57536 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 5 ms 20920 KB Output is correct
5 Correct 4 ms 20944 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20824 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 5 ms 20828 KB Output is correct
10 Correct 5 ms 20828 KB Output is correct
11 Correct 5 ms 20920 KB Output is correct
12 Correct 4 ms 20824 KB Output is correct
13 Correct 7 ms 20824 KB Output is correct
14 Correct 9 ms 21048 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 20828 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 7 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20968 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 129 ms 29576 KB Output is correct
24 Correct 129 ms 29544 KB Output is correct
25 Correct 147 ms 29600 KB Output is correct
26 Correct 175 ms 29944 KB Output is correct
27 Correct 140 ms 29972 KB Output is correct
28 Correct 143 ms 29940 KB Output is correct
29 Correct 984 ms 29544 KB Output is correct
30 Correct 938 ms 29624 KB Output is correct
31 Execution timed out 2033 ms 28572 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 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 5 ms 20920 KB Output is correct
5 Correct 4 ms 20944 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20824 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 5 ms 20828 KB Output is correct
10 Correct 5 ms 20828 KB Output is correct
11 Correct 5 ms 20920 KB Output is correct
12 Correct 4 ms 20824 KB Output is correct
13 Correct 7 ms 20824 KB Output is correct
14 Correct 9 ms 21048 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 7 ms 20828 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 7 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20968 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 699 ms 57104 KB Output is correct
24 Correct 719 ms 57264 KB Output is correct
25 Execution timed out 2036 ms 41132 KB Time limit exceeded
26 Halted 0 ms 0 KB -