Submission #768892

#	Time	Username	Problem	Language	Result	Execution time	Memory
768892		stefdasca	Financial Report (JOI21_financial)	C++14	100 / 100	2519 ms	33276 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
int n, d, 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 lz[1200002], aint2[1200002];
 
void lazy(int nod, int st, int dr)
{
	aint2[nod] -= lz[nod];
	if(st != dr)
	{
		lz[nod << 1] += lz[nod];
		lz[nod << 1|1] += lz[nod];
	}
	lz[nod] = 0;
}
 
void build(int nod, int st, int dr)
{
	if(st == dr)
	{
		aint2[nod] = n - st + 1;
		return;
	}
	
	int mid = (st + dr) / 2;
	
	build(nod << 1, st, mid);
	build(nod << 1|1, mid+1, dr);
	
	aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
void update2(int nod, int st, int dr, int L, int R, int val)
{
	lazy(nod, st, dr);
	
	if(dr < L || st > R)
		return;
	
	if(L <= st && dr <= R)
	{
		lz[nod] += val;
		lazy(nod, st, dr);
		return;
	}
	
	int mid = (st + dr) / 2;
	
	update2(nod << 1, st, mid, L, R, val);
	update2(nod << 1|1, mid+1, dr, L, R, val);
	
	aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
 
int query2(int nod, int st, int dr, int L, int R)
{
	lazy(nod, st, dr);
	
	if(dr < L || st > R)
		return -1;
	if(L <= st && dr <= R)
		return aint2[nod];
	
	int mid = (st + dr) / 2;
	
	return max(query2(nod << 1, st, mid, L, R), query2(nod << 1|1, mid+1, dr, L, R));
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	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;
	
	build(1, 1, n);
	
	set<int> prv;
	
	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();
		}
		
		// binsearch
		
		set<int> :: iterator it = prv.lower_bound(v[i].second);
		
		int nxt = 1;
		
		if(it != prv.begin())
		{
			it--;
			nxt = *it;
		}
		
		int xx = query2(1, 1, n, v[i].second, v[i].second);
		
	//	cout << nxt << " " << v[i].second << '\n';
		
		update2(1, 1, n, nxt + 1, v[i].second, xx);
		
		prv.insert(v[i].second);
		
		int stx = 1;
		int drx = max(1, v[i].second - d);
		int L = drx;
		int R = v[i].second - 1;
		
	//	cout << L << " " << R << " " << v[i].second << '\n';
		while(stx <= drx)
		{
			int mid = (stx + drx) / 2;
			if(query2(1, 1, n, mid, max(1, v[i].second - d)) >= d)
			{
				L = mid;
				stx = mid + 1;
			}
			else
			{
				drx = mid - 1;
			}
		}
		
	//	cout << L << " " << R << " " << v[i].second << " " << query2(1, 1, n, 4, 4) << '\n';
		
		dp[v[i].second] = 1;
		
		if(R > 0)
			dp[v[i].second] += query(1, 1, n, L, R);
			
		//cout << dp[v[i].second] << '\n';
			
		//cout << dp[v[i].second] << '\n';
		
		updates.push_back(v[i].second);
		ans = max(ans, dp[v[i].second]);
	}
	
	cout << ans << '\n';
	
	return 0;
}

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