1667번: 지민이의 테러 Season IV

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXL = 2e5 + 1;
typedef long long ll;
int n, s;
struct st {
    ll lm, rm;
    int ck;
}t[MXL * 4];
void add1(int h, int l, int r, int g, ll x) {
    if (r < g || g < l) return;
    if (l == r) {
        t[h].lm = x + g;
        t[h].rm = x - g;
        return;
    }
    if (t[h].ck) {
        t[h].ck = 0;
        t[h * 2 + 1].ck = t[h * 2 + 2].ck = 1;
        t[h * 2 + 1].lm = t[h * 2 + 2].lm = t[h].lm;
        t[h * 2 + 1].rm = t[h * 2 + 2].rm = t[h].rm;
    }
    add1(h * 2 + 1, l, (l + r) / 2, g, x);
    add1(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    t[h].lm = min(t[h * 2 + 1].lm, t[h * 2 + 2].lm);
    t[h].rm = min(t[h * 2 + 1].rm, t[h * 2 + 2].rm);
}
void add2(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) {
        t[h].lm = t[h].rm = 1e15;
        t[h].ck = 1;
        return;
    }
    if (t[h].ck) {
        t[h].ck = 0;
        t[h * 2 + 1].ck = t[h * 2 + 1].ck = 1;
        t[h * 2 + 1].lm = t[h * 2 + 2].lm = t[h].lm;
        t[h * 2 + 1].rm = t[h * 2 + 2].rm = t[h].rm;
    }
    add2(h * 2 + 1, l, (l + r) / 2, gl, gr);
    add2(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr);
    t[h].lm = min(t[h * 2 + 1].lm, t[h * 2 + 2].lm);
    t[h].rm = min(t[h * 2 + 1].rm, t[h * 2 + 2].rm);
}
pair<ll, ll> query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return{ 1e15,1e15 };
    if (gl <= l&&r <= gr || t[h].ck) return{ t[h].lm,t[h].rm };
    pair<ll, ll> lt = query(h * 2 + 1, l, (l + r) / 2, gl, gr),
        rt = query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr);
    return{ min(lt.first,rt.first),min(lt.second,rt.second) };
}
int main() {
    scanf("%d%d", &n, &s);
    add2(0, 0, 2e5, 0, 2e5);
    add1(0, 0, 2e5, s + 1e5, 0);
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        x += 1e5;
        y += 1e5;
        pair<ll, ll> p = query(0, 0, 2e5, x, y);
        add1(0, 0, 2e5, x, p.first - x);
        add1(0, 0, 2e5, y, p.second + y);
        add2(0, 0, 2e5, x + 1, y - 1);
    }
    printf("%lld", min(query(0, 0, 2e5, 0, 1e5).second + 100000, query(0, 0, 2e5, 1e5, 2e5).first - 100000));
    return 0;
}