Submission #749327

#	Time	Username	Problem	Language	Result	Execution time	Memory
749327		amunduzbaev	Sequence (APIO23_sequence)	C++17	50 / 100	2096 ms	56360 KiB

sequence

#include "sequence.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#ifndef EVAL
#include "grader.cpp"
#endif
 
#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){
		assert(r < N);
		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){
		assert(r < N);
		return Max(l, r, 0, N, 1);
	}
	
	int first_less(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(min[x] > v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			push(x, lx, rx);
			if(min[x << 1] <= v) return first_less(l, r, v, lx, m, x << 1);
			else {
				assert(min[x << 1 | 1] <= v); 
				return first_less(l, r, v, m + 1, rx, x << 1 | 1);
			}
		}
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		int res = first_less(l, r, v, lx, m, x << 1);
		if(res == -1) res = first_less(l, r, v, m + 1, rx, x << 1 | 1);
		return res;
	}
	
	int first_less(int l, int r, int v){
		assert(r < N);
		return first_less(l, r, v, 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){
		assert(r < N);
		return Min(l, r, 0, N, 1);
	}
	
};
 
int sequence(int n, vector<int> a){ 
	a.insert(a.begin(), 0);
 
	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++;
		}
		
		for(int k=0;k<(int)pos.size();k++){
			int L1 = B.first_less(0, pos[k] - 1, B.Max(pos[k], n));
			int L2 = A.first_less(0, pos[k] - 1, A.Max(pos[k], n));
			if(~L1 && ~L2){
				int L = max(L1, L2);
				int l = upper_bound(pos.begin(), pos.end(), L) - pos.begin();
				res = max(res, k - l + 1);
			} 
			else {
				assert(false);
			}
		}
		
		while(i < j){
			B.add(p[i], n, -2);
			i++;
		}
	}
	
	return res;
}

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