Submission #651144

#	Time	Username	Problem	Language	Result	Execution time	Memory
651144		ymm	Financial Report (JOI21_financial)	C++17	0 / 100	4073 ms	331176 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;
multiset<int> seg[N*2];
int dp[N], a[N];
int n;

void add(int i, int x)
{
	i += N;
	while (i > 0) {
		seg[i].insert(x);
		i /= 2;
	}
}
void rem(int i, int x)
{
	i += N;
	while (i > 0) {
		seg[i].erase(seg[i].find(x));
		i /= 2;
	}
}
int get(int l, int r)
{
	l += N; r += N;
	int ans = 0;
	while (l < r) {
		if (l&1) ans = max(ans, *seg[l++].rbegin());
		if (r&1) ans = max(ans, *seg[--r].rbegin());
		l /= 2; r /= 2;
	}
	return ans;
}

int main()
{
	Loop (i,0,2*N)
		seg[i].insert(0);
	cin.tie(0) -> sync_with_stdio(false);
	int d;
	cin >> n >> d;
	vector<int> cmp;
	Loop (i,0,n) {
		cin >> a[i];
		cmp.push_back(a[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	Loop (i,0,n)
		a[i] = lower_bound(cmp.begin(),cmp.end(),a[i])-cmp.begin();
	dp[0] = 1;
	add(a[0], 1);
	Loop (i,1,n) {
		dp[i] = get(0, a[i]) + 1;
		add(a[i], dp[i]);
		if (i >= d)
			rem(a[i-d], dp[i-d]);
	}
	int ans = 0;
	Loop (i,max(0,n-d-1),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