Submission #826761

#TimeUsernameProblemLanguageResultExecution timeMemory
826761maomao90Dungeon 3 (JOI21_ho_t5)C++17
11 / 100
4029 ms4432 KiB
#include <bits/stdc++.h> using namespace std; #define REP(i, j, k) for (int i = (j); i < (k); i++) #define RREP(i, j, k) for (int i = (j); i >= (k); i--) template <class T> inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define ALL(x) x.begin(), x.end() #define SZ(x) (int) x.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef tuple<int, int, int> iii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005; const int MAXN = 500005; int n, q; int a[MAXN], b[MAXN]; int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> q; REP (i, 1, n + 1) { cin >> a[i]; } REP (i, 1, n + 1) { cin >> b[i]; } while (q--) { int s, t, u; cin >> s >> t >> u; ll ans = 0; set<ii> st; int tot = 0; REP (i, s, t) { if (a[i] > u) { ans = -1; break; } tot += INF; st.insert({b[i], INF}); int need = a[i]; while (need) { auto [cost, cnt] = *st.begin(); st.erase(st.begin()); int mn = min(need, cnt); need -= mn; cnt -= mn; ans += (ll) cost * mn; tot -= mn; if (cnt) { st.insert({cost, cnt}); } } while (tot > u - a[i]) { auto [cost, cnt] = *prev(st.end()); st.erase(prev(st.end())); int mn = min(tot - (u - a[i]), cnt); cnt -= mn; tot -= mn; if (cnt) { st.insert({cost, cnt}); } } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...