← Real problems

dmopc20c4p4

mediumgreedystackStatement on DMOJ

CP Lang

19 lineschecks
// dmopc20c4p4: after each prefix, the fewest adjacent swaps that make it valid. A value equal to
// the current run length extends the run; a larger one waits on a stack and is pulled back
// (paying its distance) once the run must grow past what is waiting.
let n = read<1..=500_000>()
var run = 0
var cost = 0
var waiting: List<Int> = []
var out: List<Int> = []
for (i, x) in read<[n]Int>().items:
    while run < x:
        cost += i - waiting.pop()!
        run += 1
    if x == run:
        run += 1
    else:
        cost += run - x - 1
        waiting.push(i)
    out.push(cost)
print(out)

Accepted C++

102 lines · 3.65 s on the judge
#include "bits/stdc++.h"

using namespace std;

//sad; long long double doesn't exist
using ld = long double;

//imagine a language where int = long
#define long long long

//typing too hard
#define endl "\n"

#define sz(x) int((x).size())

//const int maxn = 5000;
//int n;
//int bit[maxn + 1];
//
//void add(int ind) {
//	ind++;
//	while(ind <= n) {
//		bit[ind]++;
//		ind += ind & -ind;
//	}
//}
//
//int psum(int ind) {
//	int ret = 0;
//	while(ind > 0) {
//		ret += bit[ind];
//		ind -= ind & -ind;
//	}
//	return ret;
//}
//
//int lsum(int ind) {
//	return psum(n) - psum(ind);
//}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int sz = 0;
	long ans = 0;
	deque<int> last;
	for(int i = 0; i < n; i++) {
		while(sz < arr[i]) {
			int cur = last.back();
			last.pop_back();
			ans += i - cur;
			sz++;
		}
		if(arr[i] == sz) {
			sz++;
		}else {
			ans += sz - arr[i] - 1;
			last.push_back(i);
		}
		if(i) {
			cout << " ";
		}
		cout << ans;
	}
	cout << endl;
//	int sz = 0;
//	bool prev[n] {};
//	for(int i = 0; i < n; i++) {
//		for(int j = i - 1; j >= 0 && sz < arr[i]; j--) {
//			if(!prev[j]) {
//				prev[j] = true;
//				sz++;
//			}
//		}
//		memset(bit, 0, sizeof(bit));
//		if(sz == arr[i]) {
//			prev[i] = true;
//			sz++;
//		}
//		long ans = 0;
//		for(int j = 0; j <= i; j++) {
//			ans += lsum(arr[j] + 1 - prev[j]);
//			if(prev[j]) {
//				add(arr[j]);
//			}
//		}
//		if(i) {
//			cout << " ";
//		}
//		cout << ans;
//	}
//	cout << endl;
}