Submission #1210726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210726		namhh	Financial Report (JOI21_financial)	C++20	100 / 100	379 ms	25832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+1;
int n,d,a[N],st[4*N],lazy[4*N],st1[4*N],aqua[N],dp[N];
unordered_map<int,int>mp;
vector<int>v;
void down(int id){
    if(lazy[id] != -1){
    	st[2*id] = lazy[2*id];
    	st[2*id+1] = lazy[2*id+1];
    	lazy[2*id] = lazy[id];
    	lazy[2*id+1] = lazy[id];
    	lazy[id] = -1;
	}
}
void update2(int id, int l, int r, int i, int val){
	if(l > i | r < i) return;
	if(l == r){
		st1[id] = val;
		return;
	}
	int mid = (l+r)/2;
	update2(2*id,l,mid,i,val);
	update2(2*id+1,mid+1,r,i,val);
	st1[id] = min(st1[2*id],st1[2*id+1]);
}
void update1(int id, int l, int r, int i, int val){
	if(l > i | r < i) return;
	if(l == r){
		st[id] = max(st[id],val);
		return;
	}
	down(id);
	int mid = (l+r)/2;
	update1(2*id,l,mid,i,val);
	update1(2*id+1,mid+1,r,i,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
void update(int id, int l, int r, int u, int v){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] = 0;
		lazy[id] = 0;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	update(2*id,l,mid,u,v);
	update(2*id+1,mid+1,r,u,v);
	st[id] = max(st[2*id],st[2*id+1]);
}
int get(int id, int l, int r, int u, int v){
	down(id);
	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 >> d;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int dm = v.size();
	for(int i = 1; i <= n; i++) a[i] = upper_bound(v.begin(),v.end(),a[i])-v.begin();
	for(int i = 1; i <= n; i++) update2(1,1,n,i,1e9+1);
	for(int i = 1; i <= n; i++){
	    if(i >= d+1) update2(1,1,n,i-d,1e9+1);
	    update2(1,1,n,i,a[i]);
	    aqua[i] = st1[1];
	}
	//for(int i = 1; i <= n; i++) cout << aqua[i] << " ";
	int ans = 0;
	for(int i = 1; i <= n; i++){
		dp[i] = get(1,1,dm,1,a[i]-1)+1;
		if(i >= d){
			int x = aqua[i];
			update(1,1,dm,1,x-1);
		}
		update1(1,1,dm,a[i],dp[i]);
		ans = max(ans,dp[i]);
		//cout << dp[i] << " ";
	}
	cout << ans;
}

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