Submission #1210795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210795		_callmelucian	Dungeon 3 (JOI21_ho_t5)	C++17	11 / 100	4091 ms	3568 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
ll a[mn], b[mn];

ll solve (int l, int r, int U) {
    map<ll,ll> mp;
    vector<int> erased;
    ll sumCands = 0, ans = 0;

    for (int i = l; i <= r; i++) {
        if (a[i] > U) return -1;
        mp[b[i]] += U, sumCands += U;
        for (auto it = mp.rbegin(); it != mp.rend() && sumCands > U; it++) {
            ll subtract = min(it->second, sumCands - U);
            sumCands -= subtract, it->second -= subtract;
            if (!it->second) erased.push_back(it->first);
        }
        for (int u : erased) mp.erase(u);
        erased.clear();

        ll used = a[i];
        for (auto it = mp.begin(); it != mp.end() && used > 0; it++) {
            ll subtract = min(it->second, used);
            used -= subtract, it->second -= subtract, sumCands -= subtract;
            ans += 1LL * it->first * subtract;
            if (!it->second) erased.push_back(it->first);
        }
        for (int u : erased) mp.erase(u);
        erased.clear();
    }
    return ans;
}

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

    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    for (int i = 0; i < m; i++) {
        int l, r, U; cin >> l >> r >> U;
        cout << solve(l, r - 1, U) << "\n";
    }

    return 0;
}

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