oj.uz

Submission #751616

# Submission time Handle Problem Language Result Execution time Memory
751616 2023-06-01T01:41:59 Z rxlfd314 Sequence (APIO23_sequence) C++17
35 / 100
 484 ms 31560 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

int sequence(int N, vector<int> A) {
	if (N <= 2000) {
		int ans = 1;
		for (int i = 0; i < N; i++) {
			vector<int> cnt(N+1, 0);
			multiset<ari2> stuff;
			cnt[A[i]]++;
			stuff.insert({A[i], -i});
			ari2 med = {A[i], -i};
			for (int j = i+1; j < N; j++) {
				stuff.insert({A[j], -j});
				cnt[A[j]]++;
				if (ari2{A[j], -j} < med && (j - i & 1)) {
					med = *prev(stuff.find(med));
				} else if (ari2{A[j], -j} > med && !(j - i & 1)) {
					med = *next(stuff.find(med));
				}
				ans = max(ans, cnt[med[0]]);
				if (j - i & 1) {
					auto [a, b] = *next(stuff.find(med));
					ans = max(ans, cnt[a]);
				}
			}
		}
		return ans;
	}
	
	int middle = max_element(A.begin(), A.end()) - A.begin();
	bool mountain = true;	
	for (int i = middle - 1; i >= 0 && mountain; i--) {
		mountain &= A[i] <= A[i+1];
	}
	for (int i = middle + 1; i < N && mountain; i++) {
		mountain &= A[i] <= A[i-1];
	}
	if (mountain) {
		vector<int> inds[N];
		for (int i = 0; i < N; i++) {
			inds[A[i]-1].push_back(i);
		}
		
		int ans = 0;
		for (int ii = 0; ii < N; ii++) {
			if (inds[ii].size() < 2) {
				ans = max(ans, (int)inds[ii].size());
				continue;
			}
			int l1 = inds[ii][0], r1 = -1, l2 = -1, r2 = inds[ii].back();
			for (int i = 1; i < inds[ii].size(); i++) {
				if (inds[ii][i-1]+1 < inds[ii][i]) {
					r1 = inds[ii][i-1];
					l2 = inds[ii][i];
					break;
				}
			}
			if (r1 < 0) {
				ans = max(ans, r2 - l1 + 1);
			} else {
				int gap = l2 - r1 - 1;
				if (gap > r1 - l1 + 1 + r2 - l2 + 1) {
					if (l1 + N - r2 - 1 >= gap - (r1 - l1 + 1 + r2 - l2 + 1)) {
						ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
					}
				} else {
					ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
				}
				ans = max({ans, r1 - l1 + 1, r2 - l2 + 1});
			}
		}
		
		return ans;
	}
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:18:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |     if (ari2{A[j], -j} < med && (j - i & 1)) {
      |                                  ~~^~~
sequence.cpp:20:44: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |     } else if (ari2{A[j], -j} > med && !(j - i & 1)) {
      |                                          ~~^~~
sequence.cpp:24:11: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |     if (j - i & 1) {
      |         ~~^~~
sequence.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int i = 1; i < inds[ii].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
sequence.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 442 ms 392 KB Output is correct
14 Correct 426 ms 392 KB Output is correct
15 Correct 429 ms 392 KB Output is correct
16 Correct 421 ms 388 KB Output is correct
17 Correct 448 ms 396 KB Output is correct
18 Correct 373 ms 392 KB Output is correct
19 Correct 454 ms 396 KB Output is correct
20 Correct 484 ms 340 KB Output is correct
21 Correct 435 ms 388 KB Output is correct
22 Correct 425 ms 404 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 83 ms 25884 KB Output is correct
3 Correct 90 ms 25796 KB Output is correct
4 Correct 49 ms 18024 KB Output is correct
5 Correct 83 ms 24904 KB Output is correct
6 Correct 86 ms 24900 KB Output is correct
7 Correct 46 ms 18384 KB Output is correct
8 Correct 46 ms 18516 KB Output is correct
9 Correct 45 ms 18664 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 46 ms 19072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 31560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 442 ms 392 KB Output is correct
14 Correct 426 ms 392 KB Output is correct
15 Correct 429 ms 392 KB Output is correct
16 Correct 421 ms 388 KB Output is correct
17 Correct 448 ms 396 KB Output is correct
18 Correct 373 ms 392 KB Output is correct
19 Correct 454 ms 396 KB Output is correct
20 Correct 484 ms 340 KB Output is correct
21 Correct 435 ms 388 KB Output is correct
22 Correct 425 ms 404 KB Output is correct
23 Incorrect 21 ms 4332 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 442 ms 392 KB Output is correct
14 Correct 426 ms 392 KB Output is correct
15 Correct 429 ms 392 KB Output is correct
16 Correct 421 ms 388 KB Output is correct
17 Correct 448 ms 396 KB Output is correct
18 Correct 373 ms 392 KB Output is correct
19 Correct 454 ms 396 KB Output is correct
20 Correct 484 ms 340 KB Output is correct
21 Correct 435 ms 388 KB Output is correct
22 Correct 425 ms 404 KB Output is correct
23 Correct 83 ms 25884 KB Output is correct
24 Correct 90 ms 25796 KB Output is correct
25 Correct 49 ms 18024 KB Output is correct
26 Correct 83 ms 24904 KB Output is correct
27 Correct 86 ms 24900 KB Output is correct
28 Correct 46 ms 18384 KB Output is correct
29 Correct 46 ms 18516 KB Output is correct
30 Correct 45 ms 18664 KB Output is correct
31 Incorrect 46 ms 19072 KB Output isn't correct
32 Halted 0 ms 0 KB -