Submission #951488

#	Time	Username	Problem	Language	Result	Execution time	Memory
951488		SmuggingSpun	Sequence (APIO23_sequence)	C++17	28 / 100	2097 ms	9556 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
int sequence(int n, vector<int>a){
	vector<int>bit(n + 1);
	function<void(int)>update = [&] (int p){
		for(; p <= n; p += p & -p){
			bit[p]++;
		}	
	};
	function<int(int)>get = [&] (int p){
		int ans = 0;
		for(; p > 0; p -= p & -p){
			ans += bit[p];
		}	
		return ans;
	};
	function<void(int&, int)>maximize = [&] (int& a, int b){
		if(a < b){
			a = b;
		}
	};
	int ans = 0;
	for(int i = 0; i < n; i++){
		fill(bit.begin(), bit.end(), 0);
		for(int j = i; j < n; j++){
			update(a[j]);
			int low = 1, high = n, x = j - i + 1, median;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(get(mid) >= (x >> 1) + (x & 1)){
					high = (median = mid) - 1;
				}
				else{
					low = mid + 1;
				}
			}
			maximize(ans, get(median) - get(median - 1));
			if((~x & 1) && get(median) == (x >> 1)){
				low = median + 1;
				high = n;
				while(low <= high){
					int mid = (low + high) >> 1;
					if(get(mid) > (x >> 1)){
						high = (median = mid) - 1;
					}
					else{
						low = mid + 1;
					}
				}
				maximize(ans, get(median) - get(median - 1));
			}
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:39:9: warning: 'median' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     low = median + 1;
      |     ~~~~^~~~~~~~~~~~

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