Submission #372724

#	Time	Username	Problem	Language	Result	Execution time	Memory
372724		Nimbostratus	Po (COCI21_po)	C++17	20 / 70	235 ms	27756 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define ppb pop_back
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define cln(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9;
const int mod = 1e9+7;

int n,q,a[maxn],t[4*maxn],lz[4*maxn];
map<int,vector<int>> occ;

void build(int vi,int vl,int vr) {
	if(vl == vr) {
		t[vi] = a[vl];
		return; 
	}
	int mid = (vl+vr)/2;
	build(2*vi,vl,mid);
	build(2*vi+1,mid+1,vr);
	t[vi] = min(t[2*vi],t[2*vi+1]);
}

void push(int vi,int vl,int vr) {
	if(vl == vr) {
		lz[vi] = 0;
		return;
	}
	lz[2*vi] += lz[vi];
	lz[2*vi+1] += lz[vi];
	t[2*vi] += lz[vi];
	t[2*vi+1] += lz[vi];
	lz[vi] = 0;
}

void update(int vi,int vl,int vr,int l,int r,int val) {
	if(l > r) return;
	push(vi,vl,vr);
	if(vl == l and vr == r) {
		t[vi] += val;
		lz[vi] += val;
		return;
	}
	int mid = (vl+vr)/2;
	update(2*vi,vl,mid,l,min(mid,r),val);
	update(2*vi+1,mid+1,vr,max(mid+1,l),r,val);
	t[vi] = min(t[2*vi],t[2*vi+1]);
}

int query(int vi,int vl,int vr,int l,int r) {
	if(l > r) return inf;
	push(vi,vl,vr);
	if(vl == l and vr == r) return t[vi];
	int mid = (vl+vr)/2;
	return min(query(2*vi,vl,mid,l,min(mid,r)),
				query(2*vi+1,mid+1,vr,max(mid+1,l),r));
}

int solve(int l,int r,int diff) {
	if(l > r) return 0;
	int mn = query(1,1,n,l,r);
	//cout << l << " " << r << " " << mn << " " << diff << endl;
	if(l == r) return mn != 0;
	update(1,1,n,l,r,-mn);
	mn += diff;
	diff += mn - diff;
	int ans = 1;
	int st = lb(all(occ[mn]),l) - occ[mn].begin();
	int nd = ub(all(occ[mn]),r) - occ[mn].begin() - 1;
	ans += solve(l,occ[mn][st]-1,diff);
	ans += solve(occ[mn][nd]+1,r,diff);
	for(int i=st+1;i<=nd;i++) {
		ans += solve(occ[mn][i-1]+1,occ[mn][i]-1,diff);
	}
	return ans;
}

int32_t main () {
	//freopen("in","r",stdin); freopen("out","w",stdout);
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i] , occ[a[i]].pb(i);
	build(1,1,n);
	cout << solve(1,n,0) << endl;
	/*while(q--) {
		int opt,l,r,val;
		cin >> opt >> l >> r;
		if(opt == 1) {
			cin >> val;
			update(1,1,n,l,r,val);
		}
		else {
			cout << query(1,1,n,l,r) << endl;
		}
	}*/
}	
	

• Subtask 1: 20 / 70