Submission #1210127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210127		namhh	Financial Report (JOI21_financial)	C++20	5 / 100	222 ms	37388 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+1;
int n,k,a[N],b[N],st[4*N],dp[N];
vector<int>nen;
multiset<int>aqua[N];
void update(int id, int l, int r, int i, int val){
	if(l > i || r < i) return;
	if(l == r){
	    st[id] = val;
		return;
	}
	int mid = (l+r)/2;
	update(2*id,l,mid,i,val);
	update(2*id+1,mid+1,r,i,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	int mid = (l+r)/2;
	return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i =1 ; i<= n; i++){
		cin >> a[i];
		nen.push_back(a[i]);
	}
	sort(nen.begin(),nen.end());
	nen.erase(unique(nen.begin(),nen.end()),nen.end());
	int ans = 0;
	for(int i = 1; i <= n; i++) b[i] = upper_bound(nen.begin(),nen.end(),a[i])-nen.begin();
	int cc = nen.size();
	for(int i = 1; i <= n; i++){
		if(i > k+1){
			int x = b[i-k-1];
			int y = dp[i-k-1];
			aqua[x].erase(aqua[x].find(y));
			auto t = aqua[x].end();
			if(aqua[x].size()){
				--t;
			    update(1,1,cc,x,*t);
			}
			else update(1,1,cc,x,0);
		}
		dp[i] = get(1,1,cc,1,b[i]-1)+1;
		ans = max(ans,dp[i]);
		aqua[b[i]].insert(dp[i]);
		auto t = aqua[b[i]].end();
		--t;
		update(1,1,cc,b[i],*t);
	}
	cout << ans;
}

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