Submission #529986

#TimeUsernameProblemLanguageResultExecution timeMemory
529986syl123456Dungeon 3 (JOI21_ho_t5)C++17
25 / 100
534 ms35592 KiB
#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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...