Submission #2148216

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define RREP(i, a, b) for(int i = (a); i >= (b); i--)
#define pq priority_queue
#define P pair<int, int>
#define P2 pair<int, P>
#define P3 pair<int, P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF = 1e9, MOD = 1e9+7, around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
const int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
const ld PI = abs(acos(-1));
const int sqrtN = 512;
const int logN = 32;
const ll LINF=1e18;

vector<int> vec;

struct Node{
	ll ma, sum;
	
	Node(int ma, int sum) : ma(ma), sum(sum) {}
	Node operator*(const Node r) const{return Node(max(ma, r.ma), sum + r.sum);}
} e(0, 0);

struct SegmentTree{
	vector<Node> seg;
	int sz = 1;
	
	SegmentTree(int n){
		while(sz < n) sz *= 2;
		seg.assign(sz * 2, e);
	}
	
	void add(int k){
		int tmp = vec[k];
		k += sz - 1;
		seg[k] = Node(tmp, seg[k].sum + 1);
		while(k){
			k = (k - 1) / 2;
			seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
		}
	}
	
	Node get(int a, int b){
		return get(a, b, 0, 0, sz);
	}
	
	Node get(int a, int b, int k, int l, int r){
		if(b<=l||r<=a) return e;
		if(a<=l&&r<=b) return seg[k];
		
		return get(a, b, 2 * k + 1, l, (l + r) / 2) * get(a, b, 2 * k + 2, (l + r) / 2, r);
	}
};

int main(){
	int n; cin >> n;
	int a[200010]; for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) vec.push_back(a[i]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	SegmentTree seg(vec.size());
	
	int pos = lower_bound(vec.begin(), vec.end(), a[0]) - vec.begin();
	seg.add(pos);
	
	ll dp[200010] = {};
	for(int i = 1; i < n; i++){
		int k = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
		ll pos = max(0LL, seg.get(0, vec.size()).ma - a[i]);
		ll pot = seg.get(k + 1, vec.size()).sum;
		
		if(pos < pot){//increment
			if(pos){
				dp[i] = dp[i - 1] + pos;
				ll tmp = seg.get(0, vec.size()).ma;
				k = lower_bound(vec.begin(), vec.end(), tmp) - vec.begin();
				seg.add(k);
			}else{
				dp[i] = dp[i - 1] + pos;
				seg.add(k);
			}
		}else{//swap
			dp[i] = dp[i - 1] + pot;
			seg.add(k);
		}
	}
	
	//~ for(int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl;
	cout << dp[n - 1] << endl;
	return 0;
}

//dp[i + 1] = min(dp[i] + max(0, a[i - 1] - a[i]), dp[i] + (i + 1 以上の個数));

//~ 0 1 1 3
//~ 2 7 8 9 4 6 7 9 7 4 7 4 4 3 6 2 3 4 4 9

Submission Info

Judge Result