Submission #749289

#	Time	Username	Problem	Language	Result	Execution time	Memory
749289		amunduzbaev	Sequence (APIO23_sequence)	C++17	Compilation error	0 ms	0 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
//~ #define int ll
 
const int INF = 1e9;
 
struct ST{
	vector<int> min, max, p;
	int N;
	
	ST(){
		N = 5e5 + 5;
		min.resize(N << 2);
		max.resize(N << 2);
		p.resize(N << 2);
	}
	
	ST(int N): N(N) {
		min.resize(N << 2);
		max.resize(N << 2);
		p.resize(N << 2);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		min[x << 1] += p[x], max[x << 1] += p[x], p[x << 1] += p[x];
		min[x << 1 | 1] += p[x], max[x << 1 | 1] += p[x], p[x << 1 | 1] += p[x];
		p[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			min[x] += v, max[x] += v, p[x] += v;
			return;
		}
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
		min[x] = ::min(min[x << 1], min[x << 1 | 1]);
		max[x] = ::max(max[x << 1], max[x << 1 | 1]);
	}
	
	void add(int l, int r, int v){
		add(l, r, v, 0, N, 1);
	}
	
	int Max(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return -INF;
		if(lx >= l && rx <= r) return max[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return ::max(Max(l, r, lx, m, x << 1), Max(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int Max(int l, int r){
		return Max(l, r, 0, N, 1);
	}
	
	int Min(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return INF;
		if(lx >= l && rx <= r) return min[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return ::min(Min(l, r, lx, m, x << 1), Min(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int Min(int l, int r){
		return Min(l, r, 0, N, 1);
	}
};
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	vector<int> a(n + 1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	
	ST A, B;
	
	vector<int> p(n);
	iota(p.begin(), p.end(), 1);
	sort(p.begin(), p.end(), [&](int i, int j){
		if(a[i] != a[j]) return a[i] < a[j];
		return i < j;
	});
	
	for(int i=1;i<=n;i++){
		B.add(i, i, i);
		A.add(i, i, -i);
	}
	
	int res = 0;
	for(int i=0,j=0;i<n;){
		vector<int> pos;
		while(j < n && a[p[i]] == a[p[j]]){
			pos.push_back(p[j]);
			A.add(p[j], n, 2);
			j++;
		}
		
		auto check = [&](int m){
			for(int k=m - 1;k<(int)pos.size();k++){
				int l = k - m + 1, r = k;
				if(B.Max(pos[r], n) >= B.Min(0, pos[l] - 1) && A.Max(pos[r], n) >= A.Min(0, pos[l])) return true;
			}
			return false;
		};
		
		int l = 1, r = j - i;
		while(l < r){
			int m = (l + r + 1) >> 1;
			if(check(m)) l = m;
			else r = m - 1;
		}
		
		res = max(res, l);
		while(i < j){
			B.add(p[i], n, -2);
			i++;
		}
	}
	
	cout<<res<<"\n";
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccVQUzvm.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc9Ffjlm.o:sequence.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVQUzvm.o: in function `main':
grader.cpp:(.text.startup+0x2a4): undefined reference to `sequence(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status