Submission #837083

#	Time	Username	Problem	Language	Result	Execution time	Memory
837083		aZvezda	Sequence (APIO23_sequence)	C++17	0 / 100	2054 ms	52492 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e6 + 10;
vector<int> where[MAX_N];

int small[MAX_N], big[MAX_N];
int arr[MAX_N];

int sequence(int n, std::vector<int> A) {
	for(int i = 0; i < n; i ++) {
		arr[i + 1] = A[i];
	}

	for(int i = 1; i <= n; i ++) {
		where[arr[i]].push_back(i);
	}

	int ans = 0;

	for(int val = 0; val <= n; val ++) {
		if(where[val].empty()) { continue; }

		for(int i = 1; i <= n; i ++) {
			small[i] = (arr[i] < val) + small[i - 1];
			big[i] = (arr[i] > val) + big[i - 1];
		}

		for(int i = 0; i < where[val].size(); i ++) {
			int l = where[val][i];
			for(int j = i + 1; j < where[val].size(); j ++) {
				int r = where[val][j];
				if(2 * (small[r] - small[l - 1]) <= (r - l + 1) && 2 * (big[r] - big[l - 1]) <= (r - l + 1)) {
					ans = max(ans, j - i + 1);
				}
			}
		}
	}
	
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0; i < where[val].size(); i ++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~
sequence.cpp:34:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int j = i + 1; j < where[val].size(); j ++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18