Submission #749344

#	Time	Username	Problem	Language	Result	Execution time	Memory
749344		amunduzbaev	Sequence (APIO23_sequence)	C++17	50 / 100	2086 ms	58216 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);
	}
	
};
 
struct BIT{
	vector<int> tree;
	int N;
	
	BIT(){
		N = 5e5 + 5;
		tree.resize(N);
	}
	
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	int get(int l, int r){
		return get(r) - get(--l);
	}
};

int sequence(int n, vector<int> a){ 
	a.insert(a.begin(), 0);
 
	ST A, B;
	BIT cnt;
	
	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);
			cnt.add(p[j], 1);
			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));
			
			int L = max(L1, L2);
			
			assert(A.Min(0, L) <= A.Max(pos[k], n));
			assert(B.Min(0, L) <= B.Max(pos[k], n));
			assert(!L || (A.Min(0, L - 1) > A.Max(pos[k], n) || B.Min(0, L - 1) > B.Max(pos[k], n)));
			
			res = max(res, cnt.get(L + 1, pos[k]));
		}
		
		while(i < j){
			B.add(p[i], n, -2);
			cnt.add(p[i], -1);
			i++;
		}
	}
	
	return res;
}

/*
 
7
1 2 3 1 2 1 3
 
9
1 1 2 3 4 3 2 1 1
 
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
 
*/

• 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