627C - Package Delivery

code:

#include <bits/stdc++.h>
using namespace std;
#define emp emplace
#define empb emplace_back
#define umap unordered_map
#define mkp make_pair
typedef long long ll;
typedef pair<ll, ll> pll;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
typedef long double ldb;
const ll MAXN = 5e5 + 5;
mt19937_64 rd(chrono::high_resolution_clock().now().time_since_epoch().count());

#pragma GCC optimize(1,2,3,"Ofast","inline")

istream& operator>>(istream& in, __int128& x) {
	string s;
	in >> s;
	x = 0;
	for (char c : s) {
		x = x * 10 + c - 48;
	}
	return in;
}
ostream& operator<<(ostream& out, __int128 x) {
	if (!x) {
		out << "0";
		return out;
	}
	stack<char> s;
	while (x) {
		s.emp(x % 10 + 48);
		x /= 10;
	}
	while (!s.empty()) {
		out << s.top();
		s.pop();
	}
	return out;
}

struct segtree {
	ll V, l[MAXN], r[MAXN], fr[MAXN], mn[MAXN], rt, size;
	void init(ll x) {
		V = x;
		memset(l, 0, sizeof l);
		memset(r, 0, sizeof r);
		memset(fr, -1, sizeof fr);
		memset(mn, inf, sizeof mn);
		rt = 0;
		size = 0;
	}
	#define mid ((lx+rx)>>1)
	void psu(ll x) {
		if (mn[l[x]] <= mn[r[x]]) fr[x] = fr[l[x]], mn[x] = mn[l[x]];
		else fr[x] = fr[r[x]], mn[x] = mn[r[x]];
	}
	void mdf(ll p, ll v, ll& x, ll lx, ll rx) {
		if (p < lx || p > rx) return;
		if (!x) x = ++size;
		if (lx == rx) {
			fr[x] = p, mn[x] = v;
			return;
		}
		mdf(p, v, l[x], lx, mid), mdf(p, v, r[x], mid + 1, rx);
		psu(x);
	}
	void mdf(ll p, ll v) {mdf(p, v, rt, 0, V);}
	pll get(ll lb, ll rb, ll x, ll lx, ll rx) {
		if (!x) return mkp(-1, inf);
		if (lb <= lx && rx <= rb) return mkp(fr[x], mn[x]);
		auto lq = get(lb, rb, l[x], lx, mid), rq = get(lb, rb, r[x], mid + 1, rx);
		if (lq.second <= rq.second) return lq;
		return rq;
	}
	pll get(ll l, ll r) {return get(l, r, rt, 0, V);}
} st;;

ll p[MAXN], w[MAXN], d, g, n;

pll slv(ll l, ll r, ll yl) {
	if (r - l + 1 <= yl - 1) return mkp(-1, 0);
	pll ch = st.get(l, r);
	pll lq = slv(l, ch.first - 1, yl), rq = slv(ch.first + 1, r, g);
	ll jy = r + 1 - ch.first - (lq.first == -1) * (yl - ch.first);
	return mkp(lq.first == -1 ? ch.first : lq.first, lq.second + jy * ch.second + rq.second);
}

vector<ll> wj = {0};

int main() {
	cin >> d >> g >> n;
	st.init(d);
	for (ll i = 1; i <= n; ++i) cin >> p[i] >> w[i], st.mdf(p[i], w[i]), wj.empb(p[i]);
	wj.empb(d);
	sort(wj.begin(), wj.end());
	for (ll i = 1; i < wj.size(); ++i) if (wj[i] - wj[i - 1] > g) puts("-1"), exit(0);
	cout << slv(0, d - 1, g).second << endl;
	return 0;
}

isn't this segment tree + divide and conquer $$$\mathcal O(m\log d)$$$