제출 #1290292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290292		Jawad_Akbar_JJ	Financial Report (JOI21_financial)	C++20	100 / 100	206 ms	11160 KiB

Main

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;
const int N = (1<<19) + 1;
int a[N], Mn[N], Mx[N<<1], R[N], dp[N], n, d, Ans;

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i < st or i >= en)
		return;
	if (en - st == 1){
		Mx[cur] = vl;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, vl, lc, st, mid);
	insert(i, vl, rc, mid, en);
	Mx[cur] = max(Mx[lc], Mx[rc]);
}

int get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mx[cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>d;

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

	deque<int> dq;
	deque<pair<int, int>> vc;
	for (int i=1;i<=n;i++){
		while (dq.size() > 0 and a[dq.back()] >= a[i])
			dq.pop_back();
		dq.push_back(i);
		if (dq.front() <= i - d)
			dq.pop_front();
		Mn[i] = a[dq.front()];
	}

	dq.clear();
	for (int i=n;i>=1;i--){
		int l = -1, r = dq.size();
		while (l + 1 < r){
			int mid = (l + r) / 2;
			if (Mn[dq[mid]] <= a[i])
				l = mid;
			else
				r = mid;
		}
		if (r == dq.size())
			R[i] = n + 1;
		else
			R[i] = dq[r];
		while (dq.size() > 0 and Mn[dq.front()] <= Mn[i])
			dq.pop_front();
		dq.push_front(i);

		vc.push_back({-a[i], i});
	}
	sort(begin(vc), end(vc));

	for (auto [vl, i] : vc){
		dp[i] = get(i, R[i] + 1) + 1;
		insert(i, dp[i]);

		Ans = max(Ans, dp[i]);
	}
	cout<<Ans<<'\n';
}

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