# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1011407 |
2024-06-30T13:13:34 Z |
thinknoexit |
Fish 3 (JOI24_fish3) |
C++17 |
|
383 ms |
49036 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300300;
int n;
ll a[N], b[N], p[N], ans[N];
ll qs[N];
ll tree[4 * N], lazy[4 * N];
void lzy(int now, int l, int r) {
if (lazy[now] == -1) return;
tree[now] = lazy[now] * (r - l + 1);
if (l != r) lazy[2 * now] = lazy[2 * now + 1] = lazy[now];
lazy[now] = -1;
}
void update(int ql, int qr, ll w, int now = 1, int l = 1, int r = n) {
lzy(now, l, r);
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
lazy[now] = w;
lzy(now, l, r);
return;
}
int mid = (l + r) / 2;
update(ql, qr, w, 2 * now, l, mid), update(ql, qr, w, 2 * now + 1, mid + 1, r);
tree[now] = tree[2 * now] + tree[2 * now + 1];
}
ll query(int ql, int qr, int now = 1, int l = 1, int r = n) {
lzy(now, l, r);
if (l > qr || r < ql) return 0ll;
if (ql <= l && r <= qr) return tree[now];
int mid = (l + r) / 2;
return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
vector<pair<int, int>> Q[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
memset(lazy, -1, sizeof lazy);
ll d;
cin >> n >> d;
for (int i = 1;i <= n;i++) {
// c[i] = d * a[i] + b[i]
ll c;
cin >> c;
a[i] = c / d;
b[i] = c % d;
}
for (int i = 2;i <= n;i++) {
p[i] = p[i - 1];
if (b[i - 1] > b[i]) p[i]++;
}
for (int i = 1;i <= n;i++) {
a[i] -= p[i];
qs[i] = qs[i - 1] + a[i];
}
int q;
cin >> q;
for (int i = 1;i <= q;i++) {
int l, r;
cin >> l >> r;
Q[r].push_back({ l, i });
}
// do like subtask 3
int pre = 1;
stack<pair<ll, int>> st;
for (int i = 1;i <= n;i++) {
if (a[i] < 0) {
pre = i + 1;
while (!st.empty()) st.pop();
for (auto& x : Q[i]) ans[x.second] = -1;
continue;
}
while (!st.empty() && st.top().first >= a[i]) {
st.pop();
}
if (st.empty()) update(pre, i, a[i]);
else update(st.top().second + 1, i, a[i]);
st.push({ a[i], i });
for (auto& x : Q[i]) {
if (x.first < pre) ans[x.second] = -1;
else {
ans[x.second] = qs[i] - qs[x.second - 1] - query(x.second, i);
}
}
}
for (int i = 1;i <= q;i++) {
cout << ans[i] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
16732 KB |
Output is correct |
2 |
Correct |
7 ms |
16908 KB |
Output is correct |
3 |
Incorrect |
7 ms |
16732 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
383 ms |
49036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
68 ms |
31080 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
280 ms |
43092 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
16732 KB |
Output is correct |
2 |
Correct |
7 ms |
16908 KB |
Output is correct |
3 |
Incorrect |
7 ms |
16732 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |