Submission #900241

#	Time	Username	Problem	Language	Result	Execution time	Memory
900241		starchan	Sequence (APIO23_sequence)	C++17	100 / 100	904 ms	103832 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e6
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
in extremise(const in &a, const in&b)
{
	return {min(a.f, b.f), max(a.s, b.s)};
}
void increment(int delta, in &a)
{
	if(a.f == INF)
		return;
	a.f+=delta;
	a.s+=delta;
	return;
}
struct extremal_tree
{
	vector<in> tree;
	void init(int n)
	{
		tree.assign(4*n+8, {INF, -INF});
		return;
	}
	void upd(int v, int pos, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = extremise(tree[id], {v, v});
			return;
		}
		int m = (l+r)/2;
		if(pos <= m)
			upd(v, pos, 2*id, l, m);
		else
			upd(v, pos, 2*id+1, m+1, r);
		tree[id] = extremise(tree[2*id], tree[2*id+1]);
		return;
	}
	in val(int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return {INF, -INF};
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		in a = val(ql, qr, 2*id, l, m);
		in b = val(ql, qr, 2*id+1, m+1, r);
		return extremise(a, b);
	}
};
struct lazy_extremal_tree
{
	vector<in> tree;
	vector<int> lazy;
	void init(int n)
	{
		tree.assign(4*n+8, {INF, -INF});
		lazy.assign(4*n+8, 0);
		return;
	}
	void push(int id)
	{
		increment(lazy[id], tree[2*id]);
		increment(lazy[id], tree[2*id+1]);
		lazy[2*id]+=lazy[id];
		lazy[2*id+1]+=lazy[id];
		lazy[id] = 0;
		return;
	}
	void upd(int v, int pos, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = extremise(tree[id], {v, v});
			return;
		}
		int m = (l+r)/2;
		if(pos <= m)
			upd(v, pos, 2*id, l, m);
		else
			upd(v, pos, 2*id+1, m+1, r);
		tree[id] = extremise(tree[2*id], tree[2*id+1]);
		return;
	}
	void upd2(int delta, int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if(ql <= l && r <= qr)
		{
			lazy[id]+=delta;
			increment(delta, tree[id]);
			return;
		}
		push(id);
		int m = (l+r)/2;
		upd2(delta, ql, qr, 2*id, l, m);
		upd2(delta, ql, qr, 2*id+1, m+1, r);
		tree[id] = extremise(tree[2*id], tree[2*id+1]);
		return;
	}
	in val(int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return {INF, -INF};
		if(ql <= l && r <= qr)
			return tree[id];
		push(id);
		int m = (l+r)/2;
		in a = val(ql, qr, 2*id, l, m);
		in b = val(ql, qr, 2*id+1, m+1, r);
		return extremise(a, b);
	}
};

vector<int> compressor;
int compress(int n)
{
	return lower_bound(compressor.begin(), compressor.end(), n)-compressor.begin();
}
int solve(int n, vector<in> &ac, vector<in> &bd)//no assuming compression!
{
	extremal_tree work;
	compressor.clear();
	work.init(2*n);
	vector<int> v;
	
	//compress begin
	for(auto [a, c]: ac)
		v.pb(c);
	for(auto [b, d]: bd)
		v.pb(d);
	sort(v.begin(), v.end());
	compressor.pb(v[0]);
	for(int k = 1; k < v.size(); k++)
	{
		if(v[k] != v[k-1])
			compressor.pb(v[k]);
	}
	//compress over

	vector<in> a;
	vector<in> b;
	for(int i = 0; i < n; i++)
		a.pb({ac[i].f, i});
	for(int i = 0; i < n; i++)
		b.pb({bd[i].f, i});
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	int ans = -INF;

	int l = 0;
	for(int i = 0; i < n; i++)
	{
		while((l < n) && (a[l].f <= b[i].f))
		{
			work.upd(a[l].s, compress(ac[a[l].s].s), 1, 0, 2*n);
			l++;
		}
		auto [m, M] = work.val(0, compress(bd[b[i].s].s), 1, 0, 2*n);
		if(m != INF)
			ans = max(abs(m-b[i].s), ans);
		if(M != -INF)
			ans = max(abs(M-b[i].s), ans);
	}
	return ans;
}



int sequence(int n, vector<int> a)
{
	lazy_extremal_tree work;
	work.init(n);
	vector<int> adj[n+1];
	for(int i = 1; i <= n; i++)
		adj[a[i-1]].pb(i);
	for(int i = 0; i <= n; i++)
		work.upd(-i, i, 1, 0, n);
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		int m = adj[i].size();
		for(int k: adj[i-1])
			work.upd2(+1, k, n, 1, 0, n);
		for(int k: adj[i])
			work.upd2(+1, k, n, 1, 0, n);
		vector<int> bb(m+2);
		bb[0] = 0;
		bb[m+1] = n+1;
		for(int j = 1; j <= m; j++)
			bb[j] = adj[i][j-1];
		vector<in> ac(m+1), bd(m+1);
		for(int j = 0; j <= m; j++)
		{
			auto [a, b] = work.val(bb[j], bb[j+1]-1, 1, 0, n);
			ac[j] = {a+j, j-b};
			bd[j] = {b+j, j-a};
		}
		int ok = solve(m+1, ac, bd);
		ans = max(ans, ok);
	}
	return ans;
}

/*vector<int> c;
int W(int l, int r, int x)
{
	int cnt = 0;
	for(int i = l; i <= r; i++)
		cnt+=(c[i] == x);
	return cnt;
}
int median_freq(int l, int r)
{
	vector<int> v;
	int k = r-l;
	for(int i = l; i <= r; i++)
		v.pb(c[i]);
	sort(v.begin(), v.end());
	int t = k/2;
	int tp = t+k%2;
	return max(W(l, r, v[t]), W(l, r, v[tp]));
}

signed main()
{
	fast();
	int t;
	cin >> t;
	while(t--)
	{
		c.clear();
		int n;
		cin >> n;
		vector<int> a(n);
		for(int &k: a)
		{
			cin >> k;
			c.pb(k);
		}
		int ans = sequence(n, a);
		int tit = 0;
		for(int l = 0; l < n; l++)
		{
			for(int r = l; r < n; r++)
				tit = max(tit, median_freq(l, r));
		}
		if(ans != tit)
		{
			cout << "WTF !!!" << endl;
			printf("Fake = %d, real = %d", ans, tit);
		}
		assert(ans==tit);
		cout << "All good!" << endl;
	}
	return 0;
}*/	

Compilation message (stderr)

sequence.cpp: In function 'int solve(int, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
sequence.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int k = 1; k < v.size(); k++)
      |                 ~~^~~~~~~~~~

• 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