제출 #1181493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181493		patgra	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	760 ms	127256 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr ll inf = 1e18;
int n, q, maxLog;
vector<ll> dist, cost, answers, mrLeft, mrRight, prefSumDist;
vector<pair<pair<ll, ll>, pair<ll, ll>>> queries;
vector<vector<ll>> stMin, stMax;
vector<pair<pair<ll, ll>, ll>> queriesL;
vector<pair<pair<ll, ll>, pair<ll, ll>>> queriesM;
vector<ll> tr;
vector<pair<ll, ll>> t2;
vector<pair<int, int>> changes;
int tb;

void tAdd(ll i, ll x) {
    i += tb;
    while(i) tr[i] += x, i /= 2;
}

ll tQuery(ll l, ll r) {
    l += tb; r += tb;
    ll ret = tr[l];
    if(l != r) ret += tr[r];
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ret += tr[l + 1];
        if(r % 2 == 1) ret += tr[r - 1];
        l /= 2; r /= 2;
    }
    return ret;
}

void tAdd2(ll i, ll a, ll b) {
    DC << "   tAdd2(" << i << ' ' << a << ' ' << b << ") " << eol;
    a *= cost[i]; b *= cost[i];
    i += tb;
    while(i) t2[i].first += a, t2[i].second += b, i /= 2;
}

ll tQuery2(ll l, ll r, ll u) {
    DC << "   tQuery2(" << l << ' ' << r << ' ' << u << ") -> ";
    l += tb;
    r += tb;
    ll ret = t2[l].first * u + t2[l].second;
    if(l != r) ret += t2[r].first * u + t2[r].second;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ret += t2[l + 1].first * u + t2[l + 1].second;
        if(r % 2 == 1) ret += t2[r - 1].first * u + t2[r - 1].second;
        l /= 2; r /= 2;
    }
    DC << ret << eol;
    return ret;
}

ll stMinQ(ll l, ll r) {
    assert(l <= r);
    int k = 63 - __builtin_clzll(r - l + 1);
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}

ll stMaxQ(ll l, ll r) {
    assert(l <= r);
    int k = 63 - __builtin_clzll(r - l + 1);
    return max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
}

ll findMinSt(ll L, ll R) {
    ll l = L - 1, m, r = R;
    ll mn = stMinQ(L, R);
    while(r - l > 1) {
        m = (l + r) / 2;
        if(mn == stMinQ(L, m)) r = m;
        else l = m;
    }
    return r;
}

ll calcBuy(ll s, ll t, ll u, ll i) {
    ll buy;
    ll mL, mR;
    if(mrLeft[i] >= s) mL = prefSumDist[i] - prefSumDist[mrLeft[i]];
    else mL = inf;
    if(mrRight[i] <= t) mR = prefSumDist[mrRight[i]] - prefSumDist[i];
    else mR = prefSumDist[t] - prefSumDist[i];
    if(u < min(mL, mR)) buy = u;
    else if(u < max(mL, mR)) buy = min(mL, mR);
    else if(u < mL + mR) buy = mR + mL - u;
    else buy = 0;
    DC << "  at " << i << "  l = " << mL << "  r = " << mR << "  u = " << u << "  buy = " << buy << eol;
    return buy;
}

void initTree2() {
    int s = 0, t = n;
    rep(i, 0, n) {
        ll mL, mR;
        if(mrLeft[i] >= s) mL = prefSumDist[i] - prefSumDist[mrLeft[i]];
        else mL = inf;
        if(mrRight[i] <= t) mR = prefSumDist[mrRight[i]] - prefSumDist[i];
        else mR = prefSumDist[t] - prefSumDist[i];
        tAdd2(i, 1, 0);
        changes.pb({min(mL, mR), i});
        changes.pb({max(mL, mR), i});
        changes.pb({mL + mR, i});
//          if(u < min(mL, mR)) buy = u;
//          else if(u < max(mL, mR)) buy = min(mL, mR);
//          else if(u < mL + mR) buy = mR + mL - u;
//          else buy = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    tb = 1 << (64 - __builtin_clzll(n));  
    tr.resize(2 * tb);
    t2.resize(2 * tb);
    dist.resize(n);
    cost.resize(n);
    queries.resize(q);
    answers.resize(q);
    rep(i, 0, n) cin >> dist[i];
    rep(i, 0, n) cin >> cost[i];
    rep(i, 0, q) {
        int s, t, u;
        cin >> s >> t >> u;
        s--; t--;
        queries[i] = {{u, i}, {s, t}};
    }

    maxLog = 32 - __builtin_clz(n + 2);
    stMin.resize(n, vector<ll>(maxLog, inf)), stMax.resize(n, vector<ll>(maxLog, -inf));; 
    rep(i, 0, n) stMin[i][0] = cost[i], stMax[i][0] = dist[i];
    rep(k, 1, maxLog) rep(i, 0, n) stMin[i][k] = min(stMin[i][k - 1], stMin[min(n - 1, i + (1 << (k - 1)))][k - 1]), stMax[i][k] = max(stMax[i][k - 1], stMax[min(n - 1, i + (1 << (k - 1)))][k - 1]);
    mrLeft.resize(n); mrRight.resize(n);
    rep(i, 0, n) {
        int l = -1, r = i, m;
        while(r - 1 > l) {
            m = (l + r) / 2;
            if(stMinQ(m, i - 1) <= cost[i]) l = m;
            else r = m;
        }
        mrLeft[i] = l;
        l = i, r = n;
        while(r - 1 > l) {
            m = (l + r) / 2;
            if(stMinQ(i + 1, m) < cost[i]) r = m;
            else l = m;
        }
        mrRight[i] = r;
        DC << "i " << i << " mrLeft " << mrLeft[i] << " mrRight " << mrRight[i] << eol;
    }

    prefSumDist.resize(n + 1);
    prefSumDist[0] = 0;
    rep(i, 0, n) prefSumDist[i + 1] = prefSumDist[i] + dist[i];
    repIn2(ui, st, queries) {
        auto [u, qi] = ui;
        auto [s, t] = st;
        DC << "query " << qi << "  " << s << ' ' << t << ' ' << u << eol;
        ll ans = 0;
        if(stMaxQ(s, t - 1) > u) { 
            answers[qi] = -1;
            continue;
        }
        ll l = s, r = t + 1, m;
        while(r - l > 1) { 
            m = (l + r) / 2;
            if(prefSumDist[m] - prefSumDist[s] > u) r = m;
            else l = m;
        }
        auto L = l;
        l = s, r = t + 1;
        while(r - l > 1) {
            m = (l + r) / 2;
            if(prefSumDist[t] - prefSumDist[m] > u) l = m;
            else r = m;
        }
        auto R = r;
        DC << " L " << L << "  R " << R << eol;
   
        l = s - 1, r = L;
        while(r - l > 1) {
            m = (l + r) / 2;
            if(stMinQ(s, L) == stMinQ(s, m)) r = m;
            else l = m;
        }
        auto whereMin = r;
        ans += cost[whereMin] * calcBuy(s, t, u, whereMin);
        if(whereMin > s) {
            queriesL.pb({{s, whereMin - 1}, qi});
            DC << "  added qL " << s << ' ' << whereMin - 1 << eol;
        }
        L = whereMin + 1;
        R = max(R, L);
        DC << " after L ans = " << ans << "; R = " << R << eol;

        if(R < t) {
            auto minn = stMinQ(R, t - 1);
            l = R - 1, r = t - 1;
            while(r - l > 1) {
                m = (l + r) / 2;
                if(stMinQ(R, m) == minn) r = m;
                else l = m;
            }
            whereMin = r;
            ans += cost[whereMin] * calcBuy(s, t, u, whereMin);
            R = whereMin;
        }
        DC << " after R ans = " << ans << eol;

        if(L < R && l < t) {
            queriesM.pb({{u, qi}, {L, R - 1}});
            DC << "  added qM " << L << ' ' << R - 1 << " at u=" << u << eol;
        }

        answers[qi] = ans;
    }

    ranges::sort(queriesL);
    stack<ll> stck;
    ll l = 0, r = n - 1;
    while(r >= l) {
        stck.push(findMinSt(l, r));
        tAdd(stck.top(), cost[stck.top()] * (prefSumDist[r + 1] - prefSumDist[stck.top()]));
        r = stck.top() - 1;
    }
    int qli = 0;
    rep(i, 0, n) {
        while(qli < (int)queriesL.size() && queriesL[qli].first.first == i) {
            auto [lr, qi] = queriesL[qli++];
            auto [mL, mR] = lr;
            auto ad = tQuery(mL, mR);
            DC << "After queryL (" << mL << ' ' << mR << ' ' << qi << ") answer +" << ad << eol;
            answers[qi] += ad;
        }
        if(stck.top() == i) {
            stck.pop();
            l = i + 1, r = (stck.empty() ? n - 1 : stck.top() - 1);
            tAdd(i, - cost[i] * (prefSumDist[r + 1] - prefSumDist[i]));
            while(r >= l) {
                stck.push(findMinSt(l, r));
                tAdd(stck.top(), cost[stck.top()] * (prefSumDist[r + 1] - prefSumDist[stck.top()]));
                r = stck.top() - 1;
            }
        }
    }

    ranges::sort(queriesM);
    auto ci = 0;
    initTree2();
    ranges::sort(changes);

    repIn2(ui, lr, queriesM) {
        auto [u, qi] = ui;
        auto [mL, mR] = lr;
        while(ci < (ll)changes.size() && changes[ci].first <= u) {
            auto [_, ii] = changes[ci++];
            tAdd2(ii, - t2[ii + tb].first / cost[ii], - t2[ii + tb].second / cost[ii]);

            ll mL2, mR2;
            ll s = 0, t = n;
            if(mrLeft[ii] >= s) mL2 = prefSumDist[ii] - prefSumDist[mrLeft[ii]];
            else mL2 = inf;
            if(mrRight[ii] <= t) mR2 = prefSumDist[mrRight[ii]] - prefSumDist[ii];
            else mR2 = prefSumDist[t] - prefSumDist[ii];
            if(u < min(mL2, mR2)) tAdd2(ii, 1, 0);
            else if(u < max(mL2, mR2)) tAdd2(ii, 0, min(mL2, mR2));
            else if(u < mL2 + mR2) tAdd2(ii, -1, mL2 + mR2);

        }
        auto ad = tQuery2(mL, mR, u);
        DC << "After queryM (" << u << ' ' << qi << ' ' << mL << ' ' << mR << ") answer +" << ad << eol;
        DEBUG {
            rep(i, mL, mR + 1) 
                assert(tQuery2(i, i, u) == calcBuy(0, n, u, i) * cost[i]);
        }
        answers[qi] += ad;
    }

    rep(i, 0, q) cout << answers[i] << '\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44