Submission #765508

#	Time	Username	Problem	Language	Result	Execution time	Memory
765508		Drew_	Financial Report (JOI21_financial)	C++17	100 / 100	371 ms	40800 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 3e5 + 69;

int n, d;
map<int, vector<int>> sale;

struct st_max
{
	int st[2*MAX];
	inline void modify(int p, int val)
	{
		for (st[p += n] = val; p > 1; p >>= 1)
			st[p >> 1] = max(st[p], st[p ^ 1]);
	}

	inline int rmq(int l, int r) //[l, r)
	{
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1)
		{
			if (l & 1) res = max(res, st[l++]);
			if (r & 1) res = max(res, st[--r]);
		}
		return res;
	}
};

struct st_min
{
	int st[2*MAX];
	inline void modify(int p, int val)
	{
		for (st[p += n] = val; p > 1; p >>= 1)
			st[p >> 1] = min(st[p], st[p ^ 1]);
	}

	inline int rmq(int l, int r) //[l, r)
	{
		int res = 1e9;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1)
		{
			if (l & 1) res = min(res, st[l++]);
			if (r & 1) res = min(res, st[--r]);
		}
		return res;
	}
};

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> d;
	for (int i = 0; i < n; ++i)
	{
		int p; cin >> p;
		sale[p].pb(i);
	}

	st_max stmax;
	st_min stmin;
	for (int i = 0; i < 2*MAX; ++i)
		stmin.st[i] = 1e9;

	for (auto &[p, idx] : sale)
	{
		sort(idx.begin(), idx.end());

		vector<int> val, L;
		for (int x : idx)
		{
			int ql = max(0, x-d);
			while (true)
			{
				int l = stmin.rmq(ql, x);
				if (l < ql) ql = l;
				else break;
			}

			val.pb(stmax.rmq(ql, x));
			L.pb(ql);
		}

		priority_queue<ii> pq;
		for (int i = 0; i < (int)idx.size(); ++i)
		{
			while (!pq.empty() && pq.top().s2 < idx[i] - d)
				pq.pop();

			int x = val[i] + 1;
			if (!pq.empty())
				x = max(x, pq.top().f1);

			stmax.modify(idx[i], x);
			stmin.modify(idx[i], L[i]);
			pq.push({x, idx[i]});

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

	}
	cout << stmax.rmq(0, n) << '\n';

	return 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