Submission #985558

#	Time	Username	Problem	Language	Result	Execution time	Memory
985558		maomao90	Tower (JOI24_tower)	C++17	100 / 100	111 ms	17800 KiB

Main

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;

int n, q;
ll d, a, b;
ll l[MAXN], r[MAXN];
pll x[MAXN];
deque<pll> dq;
ll ans[MAXN];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> q;
    cin >> d >> a >> b;
    REP (i, 0, n) {
        cin >> l[i] >> r[i];
    }
    l[n] = LINF;
    REP (i, 0, q) {
        cin >> x[i].FI;
        x[i].SE = i;
        ans[i] = LINF;
    }
    sort(x, x + q);
    int mnq = 0, mxq = 0;
    dq.pb({0, l[0] - 1});
    int ptr = 0;
    ll jcnt = 0;
    auto cost = [&] (int id, ll jcnt) {
        mnto(ans[x[id].SE], (x[id].FI - jcnt * d) * a + jcnt * b);
    };
    auto cutfront = [&] (ll bnd) {
        while (!dq.empty() && dq.front().FI < bnd) {
            while (mxq < q && x[mxq].FI <= min(bnd - 1, dq.front().SE)) {
                if (x[mxq].FI >= dq.front().FI) {
                    cost(mxq, jcnt - 1);
                }
                mxq++;
            }
            dq.front().FI = bnd;
            if (dq.front().FI > dq.front().SE) {
                dq.pop_front();
                ptr = max(0, ptr - 1);
            }
        }
    };
    while (mnq < q && x[mnq].FI < l[0]) {
        cost(mnq++, jcnt);
    }
    int lptr = 0, rptr = 0;
    while (mxq < q && !dq.empty() && rptr < n) {
        ++jcnt;
        ll bnd = dq.back().SE + d;
        bool delta = 0;
        while (rptr < n && bnd >= r[rptr] + 1) {
            delta = 1;
            while (ptr < SZ(dq) && dq[ptr].FI <= r[rptr] + 1 - d) {
                ptr++;
            }
            ll lo = LINF;
            if (ptr && dq[ptr - 1].SE >= r[rptr] + 1 - d) {
                lo = r[rptr] + 1;
                dq.pb({lo, l[rptr + 1] - 1});
            } else if (dq[ptr].FI + d < l[rptr + 1]) {
                lo = dq[ptr].FI + d;
                dq.pb({lo, l[rptr + 1] - 1});
            }
            rptr++;
            while (mnq < q && x[mnq].FI < l[rptr]) {
                if (x[mnq].FI >= lo) {
                    cost(mnq, jcnt);
                }
                mnq++;
            }
        }
        cutfront(dq.front().FI + d);
        if (!delta) {
            break;
        }
    }
    while (mxq < q && !dq.empty()) {
        while (mxq < q && x[mxq].FI < dq.front().FI) {
            mxq++;
        }
        if (mxq == q) {
            break;
        }
        ll need;
        if (x[mxq].FI <= dq.front().SE) {
            // dq.front().FI + need * d >= x[mxq].FI
            // need >= (x[mxq].FI - dq.front().FI) / d
            need = (x[mxq].FI - dq.front().FI + d) / d;
        } else {
            need = (dq.front().SE - dq.front().FI + d) / d;
        }
        jcnt += need;
        cutfront(dq.front().FI + need * d);
    }
    REP (i, 0, q) {
        cout << (ans[i] == LINF ? -1 : ans[i]) << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:88:9: warning: unused variable 'lptr' [-Wunused-variable]
   88 |     int lptr = 0, rptr = 0;
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 38 / 38
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32