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)$$$
