Submission #4363922

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct Imos2DPreLoadingQueryAllGet {

    struct LazySegTree { // [L,R)
        vector<int> xdic, ydic;
        vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
        void update(int a, int b, V v, int k, int l, int r) {
            push(k, l, r); if (r <= a || b <= l) return;
            if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
            else {
                update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
                dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
            }
        }
        V get(int a, int b, int k, int l, int r) {
            push(k, l, r); if (r <= a || b <= l) return def;
            if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
            auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);
        }
        void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
        V get(int a, int b) { return get(a, b, 0, 0, NV); }
        // ---- Template ---------------------------------------------------------------------------------


        // 区間flip（0or1）,区間和 with 座圧
        const V def = 0, ldef = 0;
        V comp(V l, V r) { return l + r; }
        void setLazy(int i, V v) { lazy[i] ^= v; }
        void push(int k, int l, int r) {
            // modify------------------------------
            if (0 < lazy[k]) dat[k] = (xdic[r] - xdic[l]) - dat[k];
            // ------------------------------------
            if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
            lazy[k] = ldef;
        }
    };


    LazySegTree st;
    vector<int> SY, TY, SX, TX;
    vector<vector<int>> addbuf, subbuf;
    void add(int sx, int sy, int tx, int ty) { // [sx,tx] [sy,ty]
        SY.push_back(sy);
        SX.push_back(sx);
        TY.push_back(ty);
        TX.push_back(tx);
    }
    V solve() {
        int Q = SY.size();
        
        rep(i, 0, Q) {
            st.xdic.push_back(SX[i]);
            st.xdic.push_back(TX[i] + 1);

            st.ydic.push_back(SY[i]);
            st.ydic.push_back(TY[i] + 1);
        }

        sort(all(st.xdic));
        st.xdic.erase(unique(all(st.xdic)), st.xdic.end());
        sort(all(st.ydic));
        st.ydic.erase(unique(all(st.ydic)), st.ydic.end());
        addbuf.resize(st.ydic.size());
        subbuf.resize(st.ydic.size());

        rep(k, 0, Q) {
            SX[k] = lower_bound(all(st.xdic), SX[k]) - st.xdic.begin();
            TX[k] = lower_bound(all(st.xdic), TX[k] + 1) - st.xdic.begin();

            SY[k] = lower_bound(all(st.ydic), SY[k]) - st.ydic.begin();
            TY[k] = lower_bound(all(st.ydic), TY[k] + 1) - st.ydic.begin();

            addbuf[SY[k]].push_back(k);
            subbuf[TY[k]].push_back(k);
        }

        int yn = st.ydic.size();
        int xn = st.xdic.size();

        ll res = 0;
        rep(y, 0, yn) {
            if (0 < y) {
                ll h = st.ydic[y] - st.ydic[y - 1];
                res += h * st.get(0, xn);
            }

            fore(k, addbuf[y]) st.update(SX[k], TX[k], 1);
            fore(k, subbuf[y]) st.update(SX[k], TX[k], 1);
        }
        return res;
    }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






Imos2DPreLoadingQueryAllGet<ll, 1 << 18> imos[2][2];
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int h, w, y, x;
        cin >> h >> w >> y >> x;
        x--; y--;
        
        int ax = (x + 1) / 2;
        rep(px, 0, 2) rep(py, 0, 2) {
            if (x % 2 == px and y % 2 != py) continue;
            if (x % 2 != px and y % 2 == py) continue;

            int sx = (x - px) / 2;
            if (x - px < 0) sx = 0;
            else if ((x - px) % 2 != 0) sx++;
            int sy = (y - py) / 2;
            if (y - py < 0) sy = 0;
            else if ((y - py) % 2 != 0) sy++;

            int tx = (x + w - 1 - px) / 2;
            int ty = (y + h - 1 - py) / 2;

            if (sx <= tx and sy <= ty) imos[px][py].add(sx, sy, tx, ty);
        }
    }

    ll ans = 0;
    rep(px, 0, 2) rep(py, 0, 2) ans += imos[px][py].solve();
    cout << ans << endl;
}

Submission Info

Judge Result