Submission #768850

#	Time	Username	Problem	Language	Result	Execution time	Memory
768850		stefdasca	Financial Report (JOI21_financial)	C++14	5 / 100	174 ms	10840 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int aint[1200002];

void update(int nod, int st, int dr, int poz, int val)
{
	if(st == dr)
	{
		aint[nod] = val;
		return;
	}
	
	int mid = (st + dr) / 2;
	
	if(poz <= mid)	
		update(nod << 1, st, mid, poz, val);
	else
		update(nod << 1|1, mid+1, dr, poz, val);
		
	aint[nod] = max(aint[nod << 1], aint[nod << 1|1]);
}

int query(int nod, int st, int dr, int L, int R)
{
	if(dr < L || st > R)
		return 0;
	if(L <= st && dr <= R)
		return aint[nod];
	
	int mid = (st + dr) / 2;
	
	return max(query(nod << 1, st, mid, L, R), query(nod << 1|1, mid+1, dr, L, R));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, d;
	cin >> n >> d;
	
	vector<pair<int, int> > v(n+1);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i].first;
		v[i].second = i;
	}
	
	sort(v.begin() + 1, v.begin() + n + 1);
	
	int ans = 0;
	
	vector<int> dp(n+1);
	vector<int> updates;
	
	for(int i = 1; i <= n; i++)
	{
		if(i != 1 && v[i].first > v[i-1].first)
		{
			for(auto x : updates)
				update(1, 1, n, x, dp[x]);
			updates.clear();
		}
		
		int L = max(1, v[i].second - d);
		int R = v[i].second - 1;
		
		dp[v[i].second] = 1;
		
		if(R > 0)
			dp[v[i].second] += query(1, 1, n, L, R);
		
		updates.push_back(v[i].second);
		
		ans = max(ans, dp[v[i].second]);
	}
	
	cout << ans << '\n';
	
	return 0;
}

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