Submission #2601273

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

class SegmentManager {
    const ll D;
    map<ll, ll> cnt;
    ll ans;
    ll f(ll l, ll r) {
        // assert(l < r);
        if (r - l - 1 <= D) {
            return r - l - 1;
        }
        return 0;
    }
    void s_insert(ll day) {
        // cout << "s_insert: " << day << endl;
        // assert(s.count(day) == 0);
        auto it = cnt.upper_bound(day);
        ll l = -linf, r = linf;
        // right
        if (it != cnt.end()) {
            r = it->first;
            ans += f(day, r);
        }
        // left
        if (it != cnt.begin()) {
            --it;
            l = it->first;
            ans += f(l, day);
        }
        ans -= f(l, r);
        // self
        ++ans;
    }
    void s_remove(ll day) {
        // cout << "s_remove: " << day << endl;
        // assert(s.count(day) > 0);
        auto it = cnt.upper_bound(day);
        ll l = -linf, r = linf;
        // right
        if (it != cnt.end()) {
            r = it->first;
            ans -= f(day, r);
        }
        // left
        if (it != cnt.begin()) {
            --it;
            l = it->first;
            ans -= f(l, day);
        }
        ans += f(l, r);
        // self
        --ans;
    }
public:
    SegmentManager(const ll D) : D(D), ans(0) {}
    void insert(ll day) {
        if (cnt.count(day) == 0) {
            s_insert(day);
        }
        ++cnt[day];
    }
    void remove(ll day) {
        // assert(cnt[day] > 0);
        if (--cnt[day] == 0) {
            cnt.erase(day);
            s_remove(day);
        }
    }
    ll find() {
        return ans;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll Y, W, n, m, D; cin >> Y >> W >> n >> m >> D;
    vector<ll> A(n); cin >> A;
    vector<vector<ll>> C2Bs(W);
    rep(i, n) --A[i];
    rep(i, m) {
        ll B, C; cin >> B >> C; --B, --C;
        C2Bs[C].pb(B);
    }
    SegmentManager sm(D);
    rep(C, W) each(B, C2Bs[C]) {
        sm.insert(B * W + C);
    }
    rep(d, W) {
        rep(i, n) {
            sm.insert(A[i] + d);
        }
        cout << sm.find() << endl;
        if (d+1 < W) {
            rep(i, n) {
                sm.remove(A[i] + d);
            }
            ll C = d;
            each(B, C2Bs[C]) {
                sm.remove(B * W + C);
                sm.insert(B * W + C + W);
            }
        }
    }
}

Submission Info

Judge Result