Submission #651145

#	Time	Username	Problem	Language	Result	Execution time	Memory
651145		ymm	Financial Report (JOI21_financial)	C++17	0 / 100	4027 ms	20868 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 300'010;
const int S = 4096;
multiset<int> fen[N];
int dp[N], a[N];
int ql[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx")))
int get_mx(int l, int r, int x)
{
	int ans = 0;
	Loop (i,l,r)
		ans = ans < dp[i] && a[i] < x? dp[i]: ans;
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int d;
	cin >> n >> d;
	Loop (i,0,n)
		cin >> a[i];
	vector<int> st;
	Loop (i,0,n) {
		while (st.size() && a[st.back()] < a[i])
			st.pop_back();
		ql[i] = st.size()? max(0, st.back()-d+1): 0;
		st.push_back(i);
	}
	for (int l = 0; l < n; l += S) {
		int r = min(l + S, n);
		Loop (i,l,r) {
			dp[i] = max(dp[i], get_mx(max(ql[i], l), i, a[i]));
			dp[i] += 1;
		}
		Loop (i,r,n)
			dp[i] = max(dp[i], get_mx(max(ql[i], l), r, a[i]));
	}
	int ans = 0;
	Loop (i,0,n)
		ans = max(ans, dp[i]);
	cout << ans << '\n';
}

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