Traffic jam

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define ll long long
using namespace std;

const ll inf = (ll)1e18;
const int SIZE = 604900 * 4 + 5;

int n, m, x, y, k, c, l, r;
ll st[SIZE], lazy[SIZE];

void push(int id, int l, int r) {
    if (lazy[id] != 0 && l < r) {
        int mid = (l + r) >> 1;
        int L = id<<1, R = id<<1|1;
        // cập nhật con trái bằng lazy * số phần tử con trái
        st[L] += lazy[id] * (mid - l + 1);
        lazy[L] += lazy[id];
        // cập nhật con phải
        st[R] += lazy[id] * (r - mid);
        lazy[R] += lazy[id];
        lazy[id] = 0;
    } else if (l == r) {
        // lá: chỉ cần clear
        lazy[id] = 0;
    }
}

void update(int u, int v, ll val, int id = 1, int l = 1, int r = n) {
    if (r < u || l > v) return; // không giao
    if (l >= u && r <= v) {
        st[id] += val * (r - l + 1); // tăng tổng của đoạn
        lazy[id] += val; // lưu lazy (tính theo phần tử)
        return;
    }
    push(id, l, r);
    int mid = (l + r) >> 1;
    update(u, v, val, id<<1, l, mid);
    update(u, v, val, id<<1|1, mid+1, r);
    st[id] = max(st[id<<1],st[id<<1|1]);
}

ll get(int u, int v, int id = 1, int l = 1, int r = n) {
    if (r < u || l > v) return 0; // không giao -> tổng = 0
    if (l >= u && r <= v) {
        return st[id];
    }
    push(id, l, r);
    int mid = (l + r) >> 1;
    return max(get(u, v, id<<1, l, mid),get(u, v, id<<1|1, mid+1, r));
}

int main() {
    fast;
    cin >> n;
    // khởi tạo mảng (an toàn)
    FOR(i,1,4*n+2) { st[i]=0; lazy[i]=0; }
    FOR(i,1,n) {
        cin >> x >> y;
        l=min(l,x);
        r=max(r,y);
        update(x,y,1);
    }
    cout << get(l,r);

    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: WRONG ANSWER

Test 48

Verdict: WRONG ANSWER

Test 49

Verdict: WRONG ANSWER

Test 50

Verdict: WRONG ANSWER

Test 51

Verdict: WRONG ANSWER

Test 52

Verdict: WRONG ANSWER

Test 53

Verdict: WRONG ANSWER

Test 54

Verdict: WRONG ANSWER

Test 55

Verdict: WRONG ANSWER

Test 56

Verdict: WRONG ANSWER

Test 57

Verdict: WRONG ANSWER

Test 58

Verdict: WRONG ANSWER

Test 59

Verdict: WRONG ANSWER

Test 60

Verdict: WRONG ANSWER

Test 61

Verdict: WRONG ANSWER

Test 62

Verdict: WRONG ANSWER

Test 63

Verdict: WRONG ANSWER

Test 64

Verdict: WRONG ANSWER

Test 65

Verdict: WRONG ANSWER

Test 66

Verdict: WRONG ANSWER

Test 67

Verdict: WRONG ANSWER

Test 68

Verdict: WRONG ANSWER

Test 69

Verdict: WRONG ANSWER

Test 70

Verdict: WRONG ANSWER