Submission #717569

#	Time	Username	Problem	Language	Result	Execution time	Memory
717569		Radin_Zahedi2	Financial Report (JOI21_financial)	C++17	0 / 100	4037 ms	3348 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'


int n, d;
const int N = 3e5 + 5;
int a[N];

int mini[N];
int dp[N];

void input() {
	cin >> n >> d;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
}

void cremini() {
	deque<int> dq;
	for (int i = 1; i < d; i++) {
		while (!dq.empty()) {
			if (a[dq.front()] < a[i]) {
				break;
			}

			dq.pop_front();
		}
		dq.push_front(i);
	}

	for (int i = d; i <= n; i++) {
		while (!dq.empty()) {
			if (a[dq.front()] < a[i]) {
				break;
			}

			dq.pop_front();
		}
		dq.push_front(i);

		if (dq.back() == i - d) {
			dq.pop_back();
		}

		mini[i] = a[dq.back()];
	}

	for (int i = d; i <= n; i++) {
		int tri = a[i];
		for (int j = i - d + 1; j <= i; j++) {
			tri = min(tri, a[j]);
		}

		if (tri != mini[i]) {
			throw;
		}
	}
}

void solve() {
	cremini();


	vector<int> cands;
	vector<int> obs;
	for (int i = n; i >= 1; i--) {
		int lobs = sz(obs), robs = -1;
		while (lobs - 1 != robs) {
			int m = (lobs + robs + 1) / 2;

			if (mini[obs[m]] > a[i]) {
				robs = m;
			}
			else {
				lobs = m;
			}
		}

		int limi = n + 1;
		if (robs != -1) {
			limi = obs[robs];
		}


		for (int j = i + 1; j < limi; j++) {
			if (mini[j] > a[i]) {
				throw;
			}
		}
		if (limi != n + 1 && mini[limi] <= a[i]) {
			throw;
		}


		int l = sz(cands), r = -1;
		while (l - 1 != r) {
			int m = (l + r + 1) / 2;

			if (a[cands[m]] > a[i] && cands[m] <= limi) {
				l = m;
			}
			else {
				r = m;
			}
		}

	
		if (l == sz(cands)) {
			dp[i] = 1;
		}
		else {
			dp[i] = dp[cands[l]] + 1;
		}


		while (!cands.empty()) {
			if (a[cands.back()] < a[i] && dp[cands.back()] > dp[i]) {
				break;
			}

			cands.pop_back();
		}
		cands.pb(i);

		if (i + d - 1 <= n) {
			while (!obs.empty()) {
				if (mini[i + d - 1] < mini[obs.back()]) {
					break;
				}
			
				obs.pop_back();
			}
			obs.pb(i + d - 1);
		}
	}


	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dp[i]);
	}

	cout << ans;
}

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

	input();

	solve();

	return 0;
}

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