oj.uz

답안 #884067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884067 2023-12-06T15:23:39 Z nguyentunglam 서열 (APIO23_sequence) C++17
41 / 100
 2000 ms 54968 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, pos[val][i + 1] - 1);
        int to = get_max(1, 0, n, cur, pos[val][i + 1] - 1);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20900 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 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 21080 KB Output is correct
10 Correct 4 ms 20824 KB Output is correct
11 Correct 4 ms 20824 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20900 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 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 21080 KB Output is correct
10 Correct 4 ms 20824 KB Output is correct
11 Correct 4 ms 20824 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 7 ms 20828 KB Output is correct
14 Correct 8 ms 20828 KB Output is correct
15 Correct 7 ms 20928 KB Output is correct
16 Correct 6 ms 20824 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 7 ms 21028 KB Output is correct
19 Correct 6 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20828 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 701 ms 53536 KB Output is correct
3 Correct 739 ms 54968 KB Output is correct
4 Execution timed out 2017 ms 38752 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Execution timed out 2049 ms 42172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 831 ms 52776 KB Output is correct
2 Correct 860 ms 53420 KB Output is correct
3 Correct 814 ms 53676 KB Output is correct
4 Correct 818 ms 52748 KB Output is correct
5 Correct 783 ms 54248 KB Output is correct
6 Correct 780 ms 53232 KB Output is correct
7 Correct 717 ms 53064 KB Output is correct
8 Correct 717 ms 53252 KB Output is correct

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20900 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 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 21080 KB Output is correct
10 Correct 4 ms 20824 KB Output is correct
11 Correct 4 ms 20824 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 7 ms 20828 KB Output is correct
14 Correct 8 ms 20828 KB Output is correct
15 Correct 7 ms 20928 KB Output is correct
16 Correct 6 ms 20824 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 7 ms 21028 KB Output is correct
19 Correct 6 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20828 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 131 ms 29200 KB Output is correct
24 Correct 156 ms 28988 KB Output is correct
25 Correct 133 ms 29204 KB Output is correct
26 Correct 140 ms 29720 KB Output is correct
27 Correct 139 ms 29720 KB Output is correct
28 Correct 139 ms 29716 KB Output is correct
29 Correct 894 ms 29388 KB Output is correct
30 Correct 901 ms 29460 KB Output is correct
31 Execution timed out 2033 ms 28060 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20900 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 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 21080 KB Output is correct
10 Correct 4 ms 20824 KB Output is correct
11 Correct 4 ms 20824 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 7 ms 20828 KB Output is correct
14 Correct 8 ms 20828 KB Output is correct
15 Correct 7 ms 20928 KB Output is correct
16 Correct 6 ms 20824 KB Output is correct
17 Correct 7 ms 20828 KB Output is correct
18 Correct 7 ms 21028 KB Output is correct
19 Correct 6 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20828 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct
23 Correct 701 ms 53536 KB Output is correct
24 Correct 739 ms 54968 KB Output is correct
25 Execution timed out 2017 ms 38752 KB Time limit exceeded
26 Halted 0 ms 0 KB -