Submission #467944

#	Time	Username	Problem	Language	Result	Execution time	Memory
467944		Vladithur	Safety (NOI18_safety)	C++17	17 / 100	663 ms	24864 KiB

safety

//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target ("sse4")
//#pragma GCC optimize("unroll-loops")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define RINIT mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;

struct chash {
    static inline uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    inline size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
 
    inline size_t operator()(const pair<uint64_t, uint64_t> &v) const {
        chash int_hasher;
        return int_hasher(v.first) * 31 + int_hasher(v.second);
    }
};

//template <class K>
//using hash_set = gp_hash_table<K, null_type, chash>;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e14;
const ll mod = 1e9+7, mod2 = 998244353;
const ld eps = 1e-9;
const bool local = false;

//RINIT;
const int logn = 21, maxn = 200001, maxm = 1, maxn2 = 3;	

struct node {
	ll v, prop;
	int size, pr;
	node *l, *r;
	
	node (int x, node * tl = nullptr, node * tr = nullptr) {
		size = 1;
		v = x;
		prop = 0;
		pr = rand();
		l = tl;
		r = tr;
	}
};

int size(node * t) {
	if (t) return t->size;
	return 0;
}

void recalc(node * t) {
	if (!t) return;
	t->size = 1 + size(t->l) + size(t->r);
}

void prop(node * t) {
	if (!t || !t->prop) return;
	t->v += t->prop;
	if (t->l) t->l->prop += t->prop;
	if (t->r) t->r->prop += t->prop;
	t->prop = 0;
}

// We want to split of the first 'n' ellements
array<node *, 2> split(node * t, int n) {
	if (!t) return {nullptr, nullptr};
	prop(t);
	if (size(t->l) >= n) {
		auto res = split(t->l, n);
		t->l = res[1];
		recalc(t);
		return {res[0], t};
	} else {
		auto res = split(t->r, n - size(t->l) - 1);
		t->r = res[0];
		recalc(t);
		return {t, res[1]};
	}
}

// Merge two treaps
node * merge(node *a, node *b) {
	if (!a) return b;
	if (!b) return a;
	prop(a); prop(b);
	if (a->pr < b->pr) {
		a->r = merge(a->r, b);
		recalc(a);
		return a;
	} else {
		b->l = merge(a, b->l);
		recalc(b);
		return b;
	}
}

// Add 'x' on [l; r)
node *update(node * t, int l, int r, int x) {
	if (l >= r) return t;
	auto a = split(t, l);
	auto b = split(a[1], r - l);
	//cout << "U: " << size(a[0]) << ' ' << size(b[0]) << ' ' << size(b[1]) << endl;
	b[0]->prop += x;
	return merge(a[0], merge(b[0], b[1]));
}

// Get first index with value > x
int tres = 0;
void find(node * t, int x, int ti = 0) {
	if (!t) return;
	if (t->v + t->prop > x) {
		tres = min(tres, size(t->l) + ti);
		find(t->l, x, ti);
	} else {
		find(t->r, x, ti + size(t->l) + 1);
	}
}

void print(node * t) {
	if (!t) return;
	prop(t);
	print(t->l);
	cout << t->v << ' ';
	print(t->r);
}

vector<ll> ta;
void toArray(node * t, ll tp = 0) {
	if (!t) return;
	tp += t->prop;
	toArray(t->l, tp);
	ta.push_back(t->v + tp);
	toArray(t->r, tp);
	delete t;
}

int main() {
	FAST;
	srand(0);
	
	int n, h;
	cin >> n >> h;
	
	ll k = -1, b;
	cin >> b;
	node * t = new node(b);
	t = merge(t, new node(b));
	
	for (int i = 1; i < n; i++) {
		ll a;
		cin >> a;
		
		//print(t);
		//cout << nl;
			
		int ti = abs(k) - 1;
		//cout << 0 << ' ' << ti + 1 << ' ' << ti + 1 << ' ' << i * 2 << endl;
		t = update(t, 0, ti + 1, -h);
		t = update(t, ti + 1, i * 2, +h);

		//print(t);
		//cout << nl;

		
		tres = inf;
		find(t, a);
		
		// cout << tres << nl;
		
		node * t2 = new node(a);
		t2 = merge(t2, new node(a));
		if (tres == inf) {
			t = merge(t, t2);
		} else {
			auto c = split(t, tres);
			c[0] = merge(c[0], t2);
			t = merge(c[0], c[1]);
		}
		b += k * h;	
		k--;
		b += a;
		//print(t);
		//cout << nl;
		//cout << "F: " << k << ' ' << b << nl << nl;
		
	}
	
	ll ans = inf2;
	
	toArray(t);
	for (ll x: ta) {
		ans = min(ans, x * k + b);
		k++;
		b -= x;
	}
	cout << ans << nl;
}

// © Benq 
/* stuff you should look for
	* int overflow, array bounds	
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29