Submission #1210137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210137		namhh	Financial Report (JOI21_financial)	C++20	5 / 100	175 ms	11640 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],dem[N],mx[N];
vector<int>nen;
void update(int id, int l, int r, int i, int val, int type){
	if(l > i || r < i) return;
	if(l == r){
	    if(type) st[id] = max({st[id],val,mx[l]});
	    else st[id] = 0;
		return;
	}
	int mid = (l+r)/2;
	update(2*id,l,mid,i,val,type);
	update(2*id+1,mid+1,r,i,val,type);
	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];
			dem[x]--;
			if(dem[x] == 0) update(1,1,cc,x,0,0);
		}
		dp[i] = get(1,1,cc,1,b[i]-1)+1;
		ans = max(ans,dp[i]);
		update(1,1,cc,b[i],dp[i],1);
		mx[b[i]] = max(mx[b[i]],dp[i]);
		dem[b[i]]++;
	}
	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