Submission #1196399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196399		Zero_OP	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	4094 ms	14172 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif //LOCAL

    int N, M;
    cin >> N >> M;
    vl X(N+1), B(N), A(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    for(int i = 0; i < N; ++i) X[i+1] = X[i] + A[i];
    for(int i = 0; i < N; ++i) cin >> B[i];



    for(int _ = 0; _ < M; ++_){
        int S, T, U;
        cin >> S >> T >> U;

        --S, --T;
        vector<tuple<int, int, int>> events;
        for(int i = S; i < T; ++i){
            events.eb(X[i], -1, B[i]);
            events.eb(min(X[i] + U, X[T]), +1, B[i]);
            events.eb(X[i+1], 0, 0);
        }

        multiset<int> v;
        sort(all(events));
        int last = -1;
        ll ans = 0;
        for(auto [t, type, cost] : events){
            if(last != -1 && last != t){
                if(v.empty()){
                    ans = -1;
                    break;
                }

                ans += 1LL * (*v.begin()) * (t - last); 
            }

            if(type == -1) v.insert(cost);
            if(type == +1) v.erase(v.lower_bound(cost));
            last = t;
        }

        cout << ans << '\n';
    }

    return 0;
}

/*

Transformed Problem : 
- Given \sum_{A[i]} points
- Each query (S, T, U) : calculate the minimum cost to cover [X[S], X[T]], we have N segments 
[X[i], X[i]+U] with cost B[i] for each element. 

*/

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