Submission #1158687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158687		Der_Vlapos	Financial Report (JOI21_financial)	C++20	100 / 100	412 ms	30956 KiB

Main

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

#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back

#define int ll

int MOD7 = 1e9 + 7;
int MODFFT = 998244353;
const int INF = 1e18 + 10;

struct segTree
{
	vector<int> tree;
	int sz = 0;

	void init(int n)
	{
		sz = n;
		tree.resize(2 * sz);
	}

	void set(int pos, int val, bool forced)
	{
		pos += sz;
		if (!forced)
			tree[pos] = max(tree[pos], val);
		else
			tree[pos] = val;
		pos >>= 1;
		while (pos)
		{
			tree[pos] = max(tree[pos * 2], tree[pos * 2 + 1]);
			pos >>= 1;
		}
	}

	int get(int l, int r)
	{
		int res = 0;
		l += sz;
		r += sz;
		while (l < r)
		{
			if (l & 1)
				res = max(res, tree[l++]);
			if (r & 1)
				res = max(res, tree[--r]);
			l >>= 1;
			r >>= 1;
		}
		return res;
	}
};

struct DSU
{
	vector<int> p, rightMost;

	void init(int n)
	{
		p.resize(n);
		rightMost.resize(n);
		for (int i = 0; i < n; ++i)
			p[i] = rightMost[i] = i;
	}

	int getR(int a)
	{
		return p[a] == a ? a : p[a] = getR(p[a]);
	}

	void merge(int a, int b)
	{
		a = getR(a);
		b = getR(b);
		p[b] = a;
		rightMost[a] = max(rightMost[a], rightMost[b]);
	}
};

struct test
{
	void solve()
	{
		int n, d;
		cin >> n >> d;
		vector<int> a(n);
		vector<int> vals;
		for (int i = 0; i < n; ++i)
		{
			cin >> a[i];
			vals.pb(a[i]);
		}
		sort(all(vals));
		vals.pb(INF);
		vals.erase(unique(all(vals)), vals.end());
		for (int &el : a)
			el = lower_bound(all(vals), el) - a.begin();

		vector<int> r(n);
		{
			vector<pii> ord;
			{
				int i = 0;
				for (int &el : a)
					ord.pb({el, -(i++)});
			}
			sort(all(ord));
			set<int> poses;
			DSU dsu;
			dsu.init(n);
			for (auto [v, i] : ord)
			{
				i = -i;
				auto it = poses.insert(i).f;
				if (it != poses.begin() and (i - *prev(it)) <= d)
					dsu.merge(*prev(it), i);
				if (next(it) != poses.end() and *next(it) - i <= d)
					dsu.merge(*next(it), i);
				r[i] = min(n - 1, dsu.rightMost[dsu.getR(i)] + d);
			}
		}
		{
			vector<pii> ord;
			{
				int i = 0;
				for (int &el : a)
					ord.pb({el, -(i++)});
			}
			sort(all(ord));
			reverse(all(ord));
			segTree tree;
			tree.init(n);
			int ans = 1;
			for (auto [v, i] : ord)
			{
				i = -i;
				int val = tree.get(i, r[i] + 1) + 1;
				ans = max(ans, val);
				tree.set(i, val, 1);
			}

			cout << ans << "\n";
		}
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

Main.cpp:154:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  154 | main()
      | ^~~~

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