Submission #341575

#	Time	Username	Problem	Language	Result	Execution time	Memory
341575		nandonathaniel	Money (IZhO17_money)	C++14	45 / 100	1553 ms	50668 KiB

money

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int a[MAXN],mini,maxi,kel[MAXN],terakhir[MAXN],tree[2][4*MAXN],lazy[4*MAXN];

set<int> S;

bool valid(){
	if(mini==maxi)return true;
	auto it=S.upper_bound(mini);
	auto it2=S.lower_bound(maxi);
	return it==it2;
}

void build(int now,int L,int R){
	if(L==R){
		tree[0][now]=tree[1][now]=1e9;
		return;
	}
	int mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[0][now]=min(tree[0][2*now],tree[0][2*now+1]);
	tree[1][now]=max(tree[1][2*now],tree[1][2*now+1]);
}

void updatetambah(int now,int val){
	tree[0][now]+=val;
	tree[1][now]+=val;
	lazy[now]+=val;
}

void updatemin(int now,int val){
	tree[0][now]=min(tree[0][now],val);
	tree[1][now]=min(tree[1][now],val);
}

void updatemax(int now,int val){
	tree[0][now]=max(tree[0][now],val);
	tree[1][now]=max(tree[1][now],val);
}
 
void pushdown(int now){
	updatetambah(2*now,lazy[now]);
	updatetambah(2*now+1,lazy[now]);
	lazy[now]=0;
	updatemin(2*now,tree[1][now]);
	updatemin(2*now+1,tree[1][now]);
	updatemax(2*now,tree[0][now]);
	updatemax(2*now+1,tree[0][now]);
}
 
void update(int now,int L,int R,int x,int y,int val){
	if(L>=x && R<=y){
		updatemin(now,val);
		return;
	}
	if(L>y || R<x)return;
	pushdown(now);
	int mid=(L+R)/2;
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[0][now]=min(tree[0][2*now],tree[0][2*now+1]);
	tree[1][now]=max(tree[1][2*now],tree[1][2*now+1]);
}

int query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[0][now];
	if(L>y || R<x)return 1e9;
	pushdown(now);
	int mid=(L+R)/2;
	return min(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)cin >> a[i];
	build(1,1,n);
	int last=1,idx=0;
	for(int i=1;i<=n;i++){
		if(i==n || a[i]>a[i+1]){
			idx++;
			for(int j=last;j<=i;j++)kel[j]=idx;
			last=i+1;
			terakhir[idx]=i;
		}
	}
	S.insert(0);
	S.insert(1e6+5);
	for(int i=0;i<n;i++){
		int ki=i+1,ka=terakhir[kel[i+1]],res=-1;
		mini=a[ki];
		while(ki<=ka){
			int mid=(ki+ka)/2;
			maxi=a[mid];
			if(valid()){
				res=mid;
				ki=mid+1;
			}
			else ka=mid-1;
		}
		int val=1;
		if(i>0)val+=query(1,1,n,i,i);
		update(1,1,n,i+1,res,val);
		S.insert(a[i+1]);
	}
	cout << query(1,1,n,n,n) << '\n';
	return 0;
}

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