Submission #4353320


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <ostream>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

template <class D, class Op> struct SimpleSeg {
    D e;
    Op op;
    int sz, lg;  // size(extended to 2^i), lg
    V<D> d;

    SimpleSeg(const V<D>& v, D _e, Op _op) : e(_e), op(_op) {
        int n = int(v.size());
        lg = 1;
        while ((1 << lg) < n) lg++;
        sz = 1 << lg;
        d = V<D>(2 * sz, e);
        for (int i = 0; i < n; i++) d[sz + i] = v[i];
        for (int i = sz - 1; i >= 0; i--) {
            update(i);
        }
    }

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

    void set(int p, D x) {
        p += sz;
        d[p] = x;
        for (int i = 1; i <= lg; i++) update(p >> i);
    }

    D single(int p) { return d[p + sz]; }

    D sum(int a, int b) {
        D sml = e, smr = e;
        a += sz;
        b += sz;

        while (a < b) {
            if (a & 1) sml = op(sml, d[a++]);
            if (b & 1) smr = op(d[--b], smr);
            a >>= 1;
            b >>= 1;
        }
        return op(sml, smr);
    }
};

template <class D, class Op>
SimpleSeg<D, Op> get_simple_seg(V<D> v, D e, Op op) {
    return SimpleSeg<D, Op>(v, e, op);
}

template <class D, class L, class OpDD, class OpDL, class OpLL> struct SegTree {
    D e_d;
    L e_l;
    OpDD op_dd;
    OpDL op_dl;
    OpLL op_ll;
    int sz, lg;  //(2^lgに拡張後の)サイズ, lg
    V<D> d;
    V<L> lz;

    SegTree(const V<D>& v,
            D _e_d,
            L _e_l,
            OpDD _op_dd,
            OpDL _op_dl,
            OpLL _op_ll)
            : e_d(_e_d), e_l(_e_l), op_dd(_op_dd), op_dl(_op_dl), op_ll(_op_ll) {
        int n = int(v.size());
        lg = 1;
        while ((1 << lg) < n) lg++;
        sz = 1 << lg;
        d = V<D>(2 * sz, e_d);
        lz = V<L>(2 * sz, e_l);
        for (int i = 0; i < n; i++) d[sz + i] = v[i];
        for (int i = sz - 1; i >= 0; i--) {
            update(i);
        }
    }

    void all_add(int k, L x) {
        d[k] = op_dl(d[k], x);
        lz[k] = op_ll(lz[k], x);
    }
    void push(int k) {
        all_add(2 * k, lz[k]);
        all_add(2 * k + 1, lz[k]);
        lz[k] = e_l;
    }
    void update(int k) { d[k] = op_dd(d[2 * k], d[2 * k + 1]); }

    void set(int p, D x) {
        p += sz;
        for (int i = lg; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= lg; i++) update(p >> i);
    }

    void add(int a, int b, L x, int l, int r, int k) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            all_add(k, x);
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        add(a, b, x, l, mid, 2 * k);
        add(a, b, x, mid, r, 2 * k + 1);
        update(k);
    }
    void add(int a, int b, L x) { add(a, b, x, 0, sz, 1); }

    D single(int p) {
        p += sz;
        for (int i = lg; i >= 1; i--) push(p >> i);
        return d[p];
    }

    D sum(int a, int b, int l, int r, int k) {
        if (b <= l || r <= a) return e_d;
        if (a <= l && r <= b) return d[k];
        push(k);
        int mid = (l + r) / 2;
        return op_dd(sum(a, b, l, mid, 2 * k), sum(a, b, mid, r, 2 * k + 1));
    }
    D sum(int a, int b) { return sum(a, b, 0, sz, 1); }
};

template <class D, class L, class OpDD, class OpDL, class OpLL>
SegTree<D, L, OpDD, OpDL, OpLL> get_seg(V<D> v,
                                        D e_d,
                                        L e_l,
                                        OpDD op_dd,
                                        OpDL op_dl,
                                        OpLL op_ll) {
    return SegTree<D, L, OpDD, OpDL, OpLL>(v, e_d, e_l, op_dd, op_dl, op_ll);
}

struct Q {
    ll h, w, r, c;

    friend ostream &operator<<(ostream &os, const Q &q) {
        os << "h: " << q.h << " w: " << q.w << " r: " << q.r << " c: " << q.c;
        return os;
    }
};

ll solve(V<Q> qu) {
    //cout << qu << endl;
    V<ll> idx = {0, TEN(9)};
    struct E {
        ll x;
        Q q;
    };
    V<E> ev;
    for (auto q: qu) {
        idx.push_back(q.h);
        idx.push_back(q.h + q.r);
        ev.push_back(E{q.w, q});
        ev.push_back(E{q.w + q.c, q});
    }
    sort(ev.begin(), ev.end(), [&](E a, E b) {
        return a.x < b.x;
    });
    sort(idx.begin(), idx.end());
    idx.erase(unique(idx.begin(), idx.end()), idx.end());
    auto get_i = [&](ll x) {
        return lower_bound(idx.begin(), idx.end(), x) - idx.begin();
    };
    int m = int(idx.size()) - 1;
    using P = pair<ll, ll>;
    V<P> seg_base(m);
    for (int i = 0; i < m; i++) {
        seg_base[i] = P(0, idx[i + 1] - idx[i]);
    }
    auto seg = get_seg(seg_base, P(0, 0), false,
            [&](P a, P b) { return P(a.first + b.first, a.second + b.second); },
            [&](P a, bool f){
                if (!f) return P(a.first, a.second);
                return P(a.second - a.first, a.second);
            },
                       [&](bool f, bool g) {
                           return f ^ g;
                       });
    ll ans = 0;
    ll bk = 0;
    for (auto e: ev) {
        ll x = e.x;
        //cout << "add " << x << " - " << bk << " " << seg.sum(0, m).first << endl;
        ans += seg.sum(0, m).first * (x - bk);
        int le = get_i(e.q.h), ri = get_i(e.q.h + e.q.r);
        //cout << "flip " << le << " " << ri << endl;
        seg.add(le, ri, true);
        bk = x;
    }
    //cout << "ans " << ans << endl;
    return ans;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;

    int n;
    cin >> n;
    V<Q> qu_b(n);
    for (int i = 0; i < n; i++) {
        ll h, w, r, c;
        cin >> r >> c >> h >> w;
        qu_b[i] = {h, w, r, c};
    }

    ll sm = 0;
    for (int dx = 0; dx <= 1; dx++) {
        for (int dy = 0; dy <= 1; dy++) {
            V<Q> qu;
            for (auto q: qu_b) {
                if ((q.h + q.w) % 2  != (dx + dy) % 2) continue;
                ll h = q.h, w = q.w, r = q.r, c = q.c;
                if (h % 2 != dy) {
                    h++; r--;
                }
                if (w % 2 != dx) {
                    w++; c--;
                }
                qu.push_back({h / 2, w / 2, (r + 1) / 2, (c + 1) / 2});
            }
            sm += solve(qu);
        }
    }
    cout << sm << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Checkered Stamps
User yosupo
Language C++14 (GCC 5.4.1)
Score 800
Code Size 6857 Byte
Status
Exec Time 668 ms
Memory 22884 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 800 / 800 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 5 ms 512 KB
16.txt 657 ms 22840 KB
17.txt 665 ms 21880 KB
18.txt 661 ms 22028 KB
19.txt 664 ms 22380 KB
20.txt 668 ms 21880 KB
21.txt 660 ms 22252 KB
22.txt 659 ms 22308 KB
23.txt 659 ms 22884 KB
24.txt 660 ms 21912 KB
25.txt 657 ms 22364 KB