Submission #526466

#	Time	Username	Problem	Language	Result	Execution time	Memory
526466		mosiashvililuka	Money (IZhO17_money)	C++14	100 / 100	191 ms	26716 KiB

money

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009],g[1000009],fen[1000009],L[1000009];
map <int, int> m;
map <int, int>::iterator it;
void upd(int q, int w){
	q=1000004-q;
	while(q<=1000005){
		fen[q]=min(fen[q],w);
		q=q+(q&(-q));
	}
}
int read(int q){
	q=1000004-q;
	int sm=1000009;
	while(q>=1){
		sm=min(sm,fen[q]);
		q=q-(q&(-q));
	}
	return sm;
}
void upd2(int q, int w){
	while(q<=1000005){
		fen[q]=max(fen[q],w);
		q=q+(q&(-q));
	}
}
int read2(int q){
	int sm=0;
	while(q>=1){
		sm=max(sm,fen[q]);
		q=q-(q&(-q));
	}
	return sm;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++) cin>>f[i];
	for(i=0; i<=1000007; i++){
		fen[i]=1000009;
	}
	for(i=1; i<=a; i++){
		g[i]=read(f[i]+1);
		g[i]=min(g[i],1000001);
		upd(f[i],f[i]);
	}
	L[1]=1;
	for(i=2; i<=a; i++){
		if(f[i]<f[i-1]){
			L[i]=i;
		}else{
			L[i]=L[i-1];
		}
	}
	for(i=0; i<=1000007; i++){
		fen[i]=0;
	}
	for(i=1; i<=a; i++){
		c=read2(f[i]-1);
		c=max(c+1,L[i]);
		dp[i]=dp[c-1]+1;
		upd2(g[i],i);
	}
	cout<<dp[a];
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55