7728번: Painting patter

https://www.acmicpc.net/problem/7728

#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
typedef long long ll;
struct sw {
    ll l, r, t, type;
    sw() {}
    sw(ll _l, ll _r, ll _t, ll _type) :
        l(_l), r(_r), t(_t), type(_type) {}
    bool operator<(sw i) const {
        return t < i.t;
    }
}l[MAX_N * 4];
struct node {
    ll sum, cnt;
}tree[MAX_N * 16];
int n, lcnt;
ll c[MAX_N * 4];
map<ll, int> mp;
void add(ll x1, ll y1, ll x2, ll y2, int type) {
    if (type % 2) x1++;
    if (type > 1) y2--;
    if (x1 % 2 != x2 % 2) x2--;
    if (y1 % 2 != y2 % 2) y1++;
    if (x1>x2 || y1 > y2) return;
    l[lcnt++] = sw(y1 / 2 + y2 % 2 * 2e9, y2 / 2 + y2 % 2 * 2e9 + 1, x1 / 2 + x1 % 2 * 2e9, 1);
    l[lcnt++] = sw(y1 / 2 + y2 % 2 * 2e9, y2 / 2 + y2 % 2 * 2e9 + 1, x2 / 2 + x1 % 2 * 2e9 + 1, -1);
}
void update(int h, ll l, ll r, ll gl, ll gr, ll x) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) tree[h].cnt += x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    tree[h].sum = tree[h].cnt ? c[r + 1] - c[l] : (l == r ? 0 : tree[h * 2 + 1].sum + tree[h * 2 + 2].sum);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        ll x1, x2, y1, y2, p;
        scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &p);
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        x1 += 1e9; x2 += 1e9 - 1;
        y1 += 1e9; y2 += 1e9 - 1;
        add(x1, y1, x2, y2, 0);
        add(x1, y1, x2, y2, p);
    }
    sort(l, l + lcnt);
    int mcnt = 0;
    for (int i = 0; i < lcnt; i++) mp[l[i].l] = mp[l[i].r] = 0;
    for (auto &it : mp) c[mcnt] = it.first, it.second = mcnt++;
    for (int i = 0; i < lcnt; i++) l[i].l = mp[l[i].l], l[i].r = mp[l[i].r] - 1;
    ll res = 0;
    for (int i = 0; i < lcnt; i++) {
        if (i) res += tree[0].sum*(l[i].t - l[i - 1].t);
        update(0, 0, mcnt - 1, l[i].l, l[i].r, l[i].type);
    }
    printf("%lld", res);
    return 0;
}