Submission #2600970

---

Source Code Expand

#include <bits/stdc++.h>

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>>;

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

    ll y, w;
    cin >> y >> w;
    VV<ll> li(2*w);
    int n, m; ll d;
    cin >> n >> m >> d;
    V<ll> base(n);
    for (int i = 0; i < n; i++) {
        cin >> base[i]; base[i]--;
    }

    for (int i = 0; i < m; i++) {
        ll b, c;
        cin >> b >> c; b--; c--;
        li[c].push_back(b*2*w+c);
        li[w+c].push_back(b*2*w+w+c);
    }

    ll ans = 0;
    map<ll, int> st;
    st[-TEN(18)] = 1;
    st[TEN(18)] = 1;
    auto di = [&](ll x, ll y) {
        assert(x != y);
        ll hx = x / (2*w), hy = y / (2*w);
        ll wx = x % (2*w), wy = y % (2*w);
        ll ans = (hy-hx) * w + (wy-wx) - 1;
        if (ans < 0) {
            cout << x << " " << y << " " << hx << " " << hy << " " << ans << endl;
        }
        assert(ans >= 0);
        return ans;
    };
    auto add = [&](ll x) {
//        cout << "ADD " << x << endl;
        if (st.count(x)) {
            st[x]++;
            return;
        }
        ll bk, nx;
        {
            auto it = st.lower_bound(x);
            nx = it->first; it--;
            bk = it->first;
        }
        st[x] = 1;
        if (di(bk, nx) <= d) return;
        ans++;
        if (di(bk, x) <= d) {
            ans += di(bk, x);
        }
        if (di(x, nx) <= d) {
            ans += di(x, nx);
        }
    };
    auto era = [&](ll x) {
//        cout << "ERA " << x << endl;
        if (st[x] > 1) {
            st[x]--;
            return;
        }
        assert(st[x] == 1);
        st.erase(x);
        ll bk, nx;
        {
            auto it = st.lower_bound(x);
            nx = it->first; it--;
            bk = it->first;
        }
        if (di(bk, nx) <= d) return;
        ans--;
        if (di(bk, x) <= d) {
            ans -= di(bk, x);
        }
        if (di(x, nx) <= d) {
            ans -= di(x, nx);
        }
    };

    auto addl = [&](int x) {
        for (ll d: li[x]) add(d);
    };
    auto eral = [&](int x) {
        for (ll d: li[x]) era(d);
    };
    for (int i = 0; i < w-1; i++) {
        addl(i);
    }

    for (int i = 0; i < w; i++) {
        addl(i+(w-1));
        for (ll d: base) {
            ll dy = d / w, dx = d % w;
            ll d2 = dy*(w*2) + (i + dx);
            add(d2);
        }
        // for (auto d: st) {
        //     cout << "(" << d.first << ", " << d.second << "), ";
        // }
        // cout << endl;
        cout << ans << endl;
        for (ll d: base) {
            ll dy = d / w, dx = d % w;            
            ll d2 = dy*(w*2) + i + dx;
            era(d2);
        }
        eral(i);
    }
    return 0;
}

Submission Info

Judge Result