robots3.c

#include <stdio.h>

int t[4 * 100000];
int tSet[4 * 100000];
long long level = 0;
int n;

int p = 1;
int m[100001];

void build(int v, int vl, int vr){
//  Построение узла дерева
    tSet[v] = 0;
    if (vl == vr) {
        t[v] = 0;
        return;
    }
    int vm = vl + (vr - vl)/2;
    build(2 * v + 1, vl, vm);
    build(2 * v + 2, vm+1, vr);
    t[v] = t[2*v+1]+t[2*v+2];
}

void push(int v, int vl, int vr) {
//  Ленивое проталкивание изменений на отрезке
    int vm = vl + (vr - vl) / 2;
    if (tSet[v] != 0) {
        t[v] = tSet[v]*(vr-vl+1);
        if (vl != vr) {
            tSet[2*v+1] = tSet[v];
            tSet[2*v+2] = tSet[v];
        }
        tSet[v] = 0;
    }
}

int query (int v, int vl, int vr, int l, int r) {
//  Запрос на получение суммы на отрезке [l, r]
    push(v, vl, vr);
    if (r < vl || vr < l)
        return 0;
    if (l <= vl && vr <= r)
        return t[v];
    int vm = vl + (vr - vl) / 2;
    long long ql = query(2*v+1, vl, vm, l, r);
    long long qr = query(2*v+2, vm+1, vr, l, r);
    return ql+qr;
}

void modify(int v, int vl, int vr, int l, int r, int val) {
//  Запрос на изменение значений на отрезке [l, r]
    push(v, vl, vr);
    if (r < vl || vr < l)
        return;
    if (l <= vl && vr <= r) {
        tSet[v] = val;
        push(v, vl, vr);
        return;
    }
    int vm = vl + (vr - vl) / 2;
    modify(2*v+1, vl, vm, l, r, val);
    modify(2*v+2, vm+1, vr, l, r, val);
    t[v] = t[2*v+1]+t[2*v+2];
}

void unbuild(int v, int vl, int vr) {
//  Распаковка дерева в массив частичных сумм m за один проход
    push(v, vl, vr);
    if (vl == vr) {
        m[p] = m[p-1]+t[v];
        ++p;
        return;
    }
    int vm = vl + (vr - vl)/2;
    unbuild(2 * v + 1, vl, vm);
    unbuild(2 * v + 2, vm+1, vr);
}

int main() {
//  freopen("in4.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    int k, l, r;
    scanf("%d%d%d", &n, &level, &k);
    build(0, 0, n-1);
    modify(0, 0, n-1, 0, level-1, -1);
    modify(0, 0, n-1, level, n-1, 1);


//  Обработка всех отрезков
    while (k--) {
        scanf("%d%d", &l, &r);
        --l; --r;
        if (l > 0 && r < n-1) { // Отрезок не касается границ
            int c = query(0, 0, n-1, l, r+1)+r;
            if (c-l+2 == 0) continue;
            c = (c+l)/2;
            modify(0, 0, n-1, l, c, 1);
            modify(0, 0, n-1, c+1,r+1,-1);
        } else if (l == 0) { // Отрезок касается левой границы
            int b = query(0, 0, n-1, 0, r+1);
            int c = r-l+2+b;
            if (c == 0) continue;
            modify(0, 0, n-1, 0, r+1, -1);
            level += c;
        } else if (r == n-1) { // ОТрезок касается правой границы
            int a = query(0, 0, n-1, 0, l-1);
            int c = r - l + 1 + a;
            if (c == query(0, 0, n-1, 0, n-1)) continue;
            modify(0, 0, n-1, l, n-1, 1);
        }
    }

//  Распаковка результата
    m[0] = 0;
    unbuild(0, 0, n-1);

//  Поиск минимума
    int i, d = n;
    for (i = 0; i < p; ++i)
        if (d > m[i])
            d = m[i];
    level += d;

//  Вывод ответа
    printf("%lld", level);
    return 0;
}