제출 #1181194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181194		patgra	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	4096 ms	86756 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;

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

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    dist.resize(n);
    cost.resize(n);
    queries.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 << "  u = " << u << eol;
        ll ans = 0;
        if(stMaxQ(s, t - 1) > u) { 
            cout << "-1\n";
            continue;
        }
        rep(i, s, t) {
            ll buy;
            ll l, r;
            if(mrLeft[i] >= s) l = prefSumDist[i] - prefSumDist[mrLeft[i]];
            else l = inf;
            if(mrRight[i] <= t) r = prefSumDist[mrRight[i]] - prefSumDist[i];
            else r = prefSumDist[t] - prefSumDist[i];
            if(r > u) {
                if(l > u) buy = u;
                else buy = l;
            }
            else {
                if(u >= r + l) buy = 0;
                else {
                    if(u < l) buy = r;
                    else buy = r + l - u;
                }
            }
            DC << " at " << i << "  l = " << l << "  r = " << r << "  buy = " << buy << eol;
            ans += cost[i] * buy;
        }
        cout << ans << '\n';
    }
}

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