Submission #750267

#	Time	Username	Problem	Language	Result	Execution time	Memory
750267		blue	Sequence (APIO23_sequence)	C++17	100 / 100	1271 ms	127472 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

#define sz(x) int(x.size())

const int inf = 10'000'000;

const int mx = 500'000;

int N;

vi A;

vi V;

struct sdata
{
	int sm = 0;

	int prefmin = 0;
	int prefmax = 0;

	int suffmin = 0;
	int suffmax = 0;

	sdata()
	{
		;
	}

	sdata(int V)
	{
		sm = V;

		prefmin = min(V, 0);
		suffmin = min(V, 0);

		prefmax = max(V, 0);
		suffmax = max(V, 0);
	}
};

sdata combine(sdata a, sdata b)
{
	sdata res;

	res.sm = a.sm + b.sm;

	res.prefmin = min(a.prefmin, a.sm + b.prefmin);
	res.prefmax = max(a.prefmax, a.sm + b.prefmax);

	res.suffmin = min(b.suffmin, b.sm + a.suffmin);
	res.suffmax = max(b.suffmax, b.sm + a.suffmax);

	return res;
}

struct segtree
{
	int l;
	int r;

	sdata v;

	segtree* left = NULL;
	segtree* right = NULL;


	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r)
			return;

		int m = (l + r)/2;

		left = new segtree(l, m);
		right = new segtree(m+1, r);
	}

	void update(int I, int V)
	{
		if(l == r)
		{
			v = sdata(V);
		}
		else
		{
			if(I <= (l+r)/2)
				left->update(I, V);
			else
				right->update(I, V);

			v = combine(left->v, right->v);
		}
	}

	sdata query(int L, int R)
	{
		if(R < L)
			return sdata(0);

		if(L <= l && r <= R)
			return v;
		else if(R <= (l+r)/2)
			return left->query(L, R);
		else if(L >= (l+r)/2 + 1)
			return right->query(L, R);
		else
			return combine(left->query(L, R), right->query(L, R));
	}
};



vvi val;

int sequence(int N_, vi A_)
{
	N = N_;
	A = vi{0};

	for(int a : A_)
		A.push_back(a);


	vi lst[1+N];
	for(int i = 1; i <= N; i++)
		lst[A[i]].push_back(i);


	segtree S(1, N);

	for(int i = 1; i <= N; i++)
		S.update(i, +1);


	int res = 0;


	for(int v = 1; v <= N; v++)
	{

		for(int i : lst[v])
			S.update(i, 0);

		for(int i : lst[v-1])
			S.update(i, -1);





		if(lst[v].empty())
			continue;



		// cerr << "\n\n\n";
		// cerr << v << " : ";
		// for(int u : lst[v])
		// 	cerr << u << ' ';
		// cerr << '\n';

		// for(int i = 1; i <= N; i++)
		// 	cerr << S.query(i, i).sm << ' ';
		// cerr << '\n';


		int H;

		vi Z{0};

		for(int i : lst[v])
			Z.push_back(i);

		H = sz(Z) - 1;

		vector<sdata> dv(1 + H);

		dv[0] = S.query(1, Z[1] - 1);

		for(int i = 1; i < H; i++)
		{
			// cerr << i << " query = " << Z[i]+1 << ' ' << Z[i+1] - 1 << '\n';
			dv[i] = S.query(Z[i] + 1, Z[i+1] - 1);
		}

		dv[H] = S.query(Z[H] + 1, N);


		vi totsum(1 + H);
		totsum[0] = 0;

		for(int i = 1; i <= H; i++)
			totsum[i] = totsum[i-1] + dv[i-1].sm;


		/*
[1] l - 1 - totsum[l] + dv[l-1].suffmin <= r - dv[r].prefmin - totsum[r]

[2] l - 1 + totsum[l] - dv[l-1].suffmax <= r + totsum[r] + dv[r].prefmax
		*/


		// cerr << "hello!\n";

		val = vvi(4, vi(1+H));
		for(int i = 1; i <= H; i++)
		{
			val[0][i] = i - 1 - totsum[i] + dv[i-1].suffmin;

			val[1][i] = i - dv[i].prefmin - totsum[i];

			val[2][i] = i - 1 + totsum[i] - dv[i-1].suffmax;

			val[3][i] = i + totsum[i] + dv[i].prefmax;
		}

		vpii lst1;

		vpii lst2;

		// cerr << "A\n";

		for(int i = 1; i <= H; i++)
		{
			lst1.push_back({val[0][i], -i});
			lst1.push_back({val[1][i], +i});

			lst2.push_back({val[2][i], -i});
			lst2.push_back({val[3][i], +i});
		}

		vi updpos(1+H), querpos(1+H);

		sort(lst1.begin(), lst1.end());
		sort(lst2.begin(), lst2.end());

		// cerr << "B\n";

		for(int i = 1; i <= sz(lst1); i++)
		{
			if(lst1[i-1].second < 0)
				updpos[-lst1[i-1].second] = i;
			else
				querpos[lst1[i-1].second] = i;
		}

		vi bit(1+2*H, 1'000'000'000);

		// cerr << "C\n";

		for(pii pp : lst2)
		{
			if(pp.second < 0)
			{
				int i = -pp.second;
				//update

				for(int j = updpos[i]; j <= 2*H; j += j&-j)
					bit[j] = min(bit[j], i);
			}
			else
			{
				int i = pp.second;
				//query

				for(int j = querpos[i]; j >= 1; j -= j&-j)
					res = max(res, i - bit[j] + 1);
			}
		}
		





		// cerr << "current res = " << res << '\n';

	}


	return res;
}

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