Submission #555331

#	Time	Username	Problem	Language	Result	Execution time	Memory
555331		blue	Financial Report (JOI21_financial)	C++17	100 / 100	391 ms	29872 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int mx = 300'000;

int N, D;

struct dsu
{
	vi par = vi(1+mx);
	vi st = vi(1+mx);
	vi mini = vi(1+mx);

	dsu()
	{
		for(int i = 1; i <= N; i++)
		{
			par[i] = i;
			st[i] = 1;
			mini[i] = i;
		}
	}

	int root(int u)
	{
		if(par[u] == u) return u;
		else return (par[u] = root(par[u]));
	}

	void join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u != v)
		{
			if(st[u] < st[v]) swap(u, v);
			par[v] = u;
			st[u] += st[v];
			mini[u] = min(mini[u], mini[v]);
		}
	}
};

int Z = (1<<19);

struct segtree
{
	vi maxv = vi(2*Z, 0);

	void update(int i, int v)
	{
		i += Z;
		for(int j = i; j >= 1; j >>= 1)
			maxv[j] = max(maxv[j], v);
	}

	int rangemax(int l, int r)
	{
		int res = 0;

		l += Z;
		r += Z+1;
		while(l < r)
		{
			if(l & 1)
			{
				res = max(res, maxv[l]);
				l++;
			}

			if(r & 1)
			{
				r--;
				res = max(res, maxv[r]);
			}

			l >>= 1;
			r >>= 1;
		}

		return res;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> D;

	vi A(1+N);
	for(int i = 1; i <= N; i++) cin >> A[i];



	vector<pii> I;
	for(int i = 1; i <= N; i++) I.push_back({A[i], -i});
	sort(I.begin(), I.end());

	int ct = 0;

	set<int> positions;

	dsu DSU;
	segtree ST;

	int res = 0;

	vi DP(1+N, 0);

	for(pii ip : I)
	{
		int i = -ip.second;

		// cerr << "i = " << i << '\n';

		auto it = positions.lower_bound(i);
		if(it != positions.end() && (*it - i) <= D)
		{
			DSU.join(i, *it);
		}

		if(it != positions.begin())
		{
			it--;
			if(i - *it <= D)
				DSU.join(i, *it);
		}

		positions.insert(i);

		int lo = DSU.mini[DSU.root(i)];

		DP[i] = 1 + ST.rangemax(lo, i-1);
		ST.update(i, DP[i]);

		res = max(res, DP[i]);

		// cerr << i << " : " << DP[i] << '\n';
	}

	cout << res << '\n';

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:108:6: warning: unused variable 'ct' [-Wunused-variable]
  108 |  int ct = 0;
      |      ^~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35