#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 : s)
cin >> i, --i;
for (int &i : t)
cin >> i, --i;
for (int &i : u)
cin >> 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
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 time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
428 KB |
Output is correct |
| 2 |
Correct |
49 ms |
476 KB |
Output is correct |
| 3 |
Correct |
19 ms |
436 KB |
Output is correct |
| 4 |
Correct |
45 ms |
440 KB |
Output is correct |
| 5 |
Correct |
31 ms |
460 KB |
Output is correct |
| 6 |
Correct |
23 ms |
448 KB |
Output is correct |
| 7 |
Correct |
46 ms |
448 KB |
Output is correct |
| 8 |
Correct |
31 ms |
484 KB |
Output is correct |
| 9 |
Correct |
19 ms |
416 KB |
Output is correct |
| 10 |
Correct |
43 ms |
456 KB |
Output is correct |
| 11 |
Correct |
49 ms |
460 KB |
Output is correct |
| 12 |
Correct |
18 ms |
460 KB |
Output is correct |
| 13 |
Correct |
35 ms |
464 KB |
Output is correct |
| 14 |
Correct |
19 ms |
460 KB |
Output is correct |
| 15 |
Correct |
20 ms |
460 KB |
Output is correct |
| 16 |
Correct |
29 ms |
452 KB |
Output is correct |
| 17 |
Correct |
31 ms |
456 KB |
Output is correct |
| 18 |
Correct |
49 ms |
460 KB |
Output is correct |
| 19 |
Correct |
16 ms |
452 KB |
Output is correct |
| 20 |
Correct |
67 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
4000 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
14948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
428 KB |
Output is correct |
| 2 |
Correct |
49 ms |
476 KB |
Output is correct |
| 3 |
Correct |
19 ms |
436 KB |
Output is correct |
| 4 |
Correct |
45 ms |
440 KB |
Output is correct |
| 5 |
Correct |
31 ms |
460 KB |
Output is correct |
| 6 |
Correct |
23 ms |
448 KB |
Output is correct |
| 7 |
Correct |
46 ms |
448 KB |
Output is correct |
| 8 |
Correct |
31 ms |
484 KB |
Output is correct |
| 9 |
Correct |
19 ms |
416 KB |
Output is correct |
| 10 |
Correct |
43 ms |
456 KB |
Output is correct |
| 11 |
Correct |
49 ms |
460 KB |
Output is correct |
| 12 |
Correct |
18 ms |
460 KB |
Output is correct |
| 13 |
Correct |
35 ms |
464 KB |
Output is correct |
| 14 |
Correct |
19 ms |
460 KB |
Output is correct |
| 15 |
Correct |
20 ms |
460 KB |
Output is correct |
| 16 |
Correct |
29 ms |
452 KB |
Output is correct |
| 17 |
Correct |
31 ms |
456 KB |
Output is correct |
| 18 |
Correct |
49 ms |
460 KB |
Output is correct |
| 19 |
Correct |
16 ms |
452 KB |
Output is correct |
| 20 |
Correct |
67 ms |
460 KB |
Output is correct |
| 21 |
Runtime error |
20 ms |
4000 KB |
Execution killed with signal 6 |
| 22 |
Halted |
0 ms |
0 KB |
- |
