Submission #536358

#	Time	Username	Problem	Language	Result	Execution time	Memory
536358		pnm1384	Financial Report (JOI21_financial)	C++14	100 / 100	559 ms	25732 KiB

Main

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

typedef long long ll;

#define F first
#define S second

const int N = 3e5 + 20;
int a[N], chap[N], rast[N], dp[N], seg[N << 2];
set<int> st, have;
pair<int, int> b[N];
int n, D;

void add(int ind, int x, int u = 1, int s = 0, int e = n)
{
	if (e - s < 2)
	{
		seg[u] = x;
		return;
	}
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	if (ind < mid)
		add(ind, x, lc, s, mid);
	else
		add(ind, x, rc, mid, e);
	seg[u] = max(seg[lc], seg[rc]);
	return;
}

int get(int l, int r, int u = 1, int s = 0, int e = n)
{
	if (e <= l || r <= s) return 0;
	if (l <= s && r >= e) return seg[u];
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> D;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = {a[i], -i};
	}
	sort(b, b + n);
	have.insert(-1); have.insert(n);
	for (int j = 0; j < n; j++)
	{
		int i = -b[j].S;
		auto it = have.lower_bound(i);
		int r = *it; it--; int l = *it;
		chap[i] = l; rast[i] = r;
		have.insert(i);
		if (r != n)
		{
			chap[r] = i;
			if (r - i <= D) st.erase(r);
		}
		if (l != -1)
		{
			rast[l] = i;
		}
		if (i - chap[i] > D) st.insert(i);
		dp[i] = 1;
		if (i != 0) 
		{
			it = st.upper_bound(i);
			if (it == st.begin())
			{
				dp[i] = max(dp[i], get(0, i) + 1);
			}
			else
			{
				it--;
				int ind = *it;
				ind = max(ind, 0);
				if (ind != i) dp[i] = max(dp[i], get(ind, i) + 1);
			}
		}
		add(i, dp[i]);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
	cout << ans;
	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