Submission #529986

#	Time	Username	Problem	Language	Result	Execution time	Memory
529986		syl123456	Dungeon 3 (JOI21_ho_t5)	C++17	25 / 100	534 ms	35592 KiB

Main

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a[n], b[n];
    for (int &i : a)
        cin >> i;
    for (int &i : b)
        cin >> i;
    if (n <= 3000 && q <= 3000) {
        ll pre[n + 1];
        pre[0] = 0;
        for (int i = 0; i < n; ++i)
            pre[i + 1] = pre[i] + a[i];
        while (q--) {
            int s, t, u;
            cin >> s >> t >> u;
            --s, --t;
            ll res = 0;
            deque<pi> q;
            for (int i = s; i < t; ++i) {
                if (a[i] > u) {
                    res = -1;
                    break;
                }
                while (!q.empty() && q.back().first >= b[i])
                    q.pop_back();
                q.emplace_back(b[i], i);
                ll tmp = 0;
                while (tmp < a[i]) {
                    while (pre[i] + tmp - pre[q.front().second] >= u)
                        q.pop_front();
                    ll x = min(a[i] - tmp, u - (pre[i] + tmp - pre[q.front().second]));
                    res += x * q.front().first;
                    tmp += x;
                }
            }
            cout << res << '\n';
        }
    }
    else {
        int s[q], t[q], u[q];
        for (int i = 0; i < q; ++i)
            cin >> s[i] >> t[i] >> u[i], --s[i], --t[i];
        assert(*min_element(u, u + q) == *max_element(u, u + q));
        int U = u[0];
        ll pre[n + 1];
        pre[0] = 0;
        for (int i = 0; i < n; ++i)
            pre[i + 1] = pre[i] + a[i];
        vector<vector<int>> qry(n);
        for (int i = 0; i < q; ++i)
            qry[s[i]].push_back(i);
        vector<pl> stk;
        map<ll, ll> suf;
        ll ans[q];
        for (int i = n - 1; ~i; --i) {
            if (a[i] > U)
                stk.clear(), suf.clear();
            int tmp = inf;
            while (!stk.empty() && stk.back().second >= b[i] && stk.back().first < pre[i] + U)
                tmp = stk.back().second, suf.erase(stk.back().first), stk.pop_back();
            if (stk.empty())
                stk.emplace_back(pre[i] + U, inf), suf[pre[i] + U] = 0;
            if (stk.back().first > pre[i] + U) {
                suf[pre[i] + U] = suf[stk.back().first] + tmp * (stk.back().first - pre[i] - U);
                stk.emplace_back(pre[i] + U, tmp);
            }
            suf[pre[i]] = suf[stk.back().first] + b[i] * (stk.back().first - pre[i]);
            stk.emplace_back(pre[i], b[i]);
            for (int j : qry[i]) {
                if (pre[t[j]] > stk[0].first) {
                    ans[j] = -1;
                    continue;
                }
                auto it = suf.upper_bound(pre[t[j]]);
                --it;
                ans[j] = suf[pre[i]] - it->second;
                auto it2 = lower_bound(all(stk), pl(it->first, inf), [](pl x, pl y) {return x > y;});
                ans[j] += it2->second * (pre[t[j]] - it->first);
            }
        }
        for (ll i : ans)
            cout << i << '\n';
    }
}
/*
sort s >
all pre, pre + u
add point, range min, ans query (range sum)

range min: prefix min
*/

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^

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