# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1011428 |
2024-06-30T13:31:22 Z |
thinknoexit |
Fish 3 (JOI24_fish3) |
C++17 |
|
551 ms |
64424 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];
ll mn[4 * N];
void build(int now = 1, int l = 1, int r = n) {
if (l == r) {
mn[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
mn[now] = min(mn[2 * now], mn[2 * now + 1]);
}
ll qmn(int ql, int qr, int now = 1, int l = 1, int r = n) {
if (l > qr || r < ql) return 1e18;
if (ql <= l && r <= qr) return mn[now];
int mid = (l + r) / 2;
return min(qmn(ql, qr, 2 * now, l, mid), qmn(ql, qr, 2 * now + 1, mid + 1, r));
}
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];
}
build();
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++) {
while (!st.empty() && st.top().first >= a[i]) {
st.pop();
}
if (st.empty()) update(1, i, a[i]);
else update(st.top().second + 1, i, a[i]);
st.push({ a[i], i });
for (auto& x : Q[i]) {
if (qmn(x.first, i) + p[x.first] < 0) {
ans[x.second] = -1;
continue;
}
ans[x.second] = qs[i] - qs[x.first - 1] - query(x.first, i);
}
}
for (int i = 1;i <= q;i++) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:80:9: warning: unused variable 'pre' [-Wunused-variable]
80 | int pre = 1;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
16728 KB |
Output is correct |
2 |
Correct |
7 ms |
16732 KB |
Output is correct |
3 |
Correct |
7 ms |
16732 KB |
Output is correct |
4 |
Correct |
9 ms |
17440 KB |
Output is correct |
5 |
Correct |
8 ms |
17244 KB |
Output is correct |
6 |
Correct |
10 ms |
17272 KB |
Output is correct |
7 |
Correct |
8 ms |
16988 KB |
Output is correct |
8 |
Correct |
8 ms |
17240 KB |
Output is correct |
9 |
Correct |
9 ms |
17244 KB |
Output is correct |
10 |
Correct |
10 ms |
17124 KB |
Output is correct |
11 |
Correct |
9 ms |
17244 KB |
Output is correct |
12 |
Correct |
9 ms |
17244 KB |
Output is correct |
13 |
Correct |
10 ms |
17244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
406 ms |
57172 KB |
Output is correct |
2 |
Correct |
406 ms |
56580 KB |
Output is correct |
3 |
Correct |
92 ms |
26856 KB |
Output is correct |
4 |
Correct |
263 ms |
56400 KB |
Output is correct |
5 |
Correct |
265 ms |
56148 KB |
Output is correct |
6 |
Incorrect |
321 ms |
54352 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
30684 KB |
Output is correct |
2 |
Correct |
435 ms |
63828 KB |
Output is correct |
3 |
Correct |
421 ms |
63824 KB |
Output is correct |
4 |
Correct |
443 ms |
63848 KB |
Output is correct |
5 |
Correct |
383 ms |
63852 KB |
Output is correct |
6 |
Correct |
404 ms |
57396 KB |
Output is correct |
7 |
Correct |
405 ms |
57428 KB |
Output is correct |
8 |
Correct |
398 ms |
60712 KB |
Output is correct |
9 |
Correct |
458 ms |
60768 KB |
Output is correct |
10 |
Correct |
473 ms |
64068 KB |
Output is correct |
11 |
Correct |
459 ms |
64252 KB |
Output is correct |
12 |
Correct |
421 ms |
64336 KB |
Output is correct |
13 |
Correct |
551 ms |
64424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
414 ms |
46928 KB |
Output is correct |
2 |
Correct |
409 ms |
57168 KB |
Output is correct |
3 |
Correct |
241 ms |
35504 KB |
Output is correct |
4 |
Correct |
382 ms |
60500 KB |
Output is correct |
5 |
Correct |
410 ms |
61812 KB |
Output is correct |
6 |
Correct |
406 ms |
63724 KB |
Output is correct |
7 |
Correct |
377 ms |
52304 KB |
Output is correct |
8 |
Correct |
436 ms |
63636 KB |
Output is correct |
9 |
Incorrect |
336 ms |
56484 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
16728 KB |
Output is correct |
2 |
Correct |
7 ms |
16732 KB |
Output is correct |
3 |
Correct |
7 ms |
16732 KB |
Output is correct |
4 |
Correct |
9 ms |
17440 KB |
Output is correct |
5 |
Correct |
8 ms |
17244 KB |
Output is correct |
6 |
Correct |
10 ms |
17272 KB |
Output is correct |
7 |
Correct |
8 ms |
16988 KB |
Output is correct |
8 |
Correct |
8 ms |
17240 KB |
Output is correct |
9 |
Correct |
9 ms |
17244 KB |
Output is correct |
10 |
Correct |
10 ms |
17124 KB |
Output is correct |
11 |
Correct |
9 ms |
17244 KB |
Output is correct |
12 |
Correct |
9 ms |
17244 KB |
Output is correct |
13 |
Correct |
10 ms |
17244 KB |
Output is correct |
14 |
Correct |
406 ms |
57172 KB |
Output is correct |
15 |
Correct |
406 ms |
56580 KB |
Output is correct |
16 |
Correct |
92 ms |
26856 KB |
Output is correct |
17 |
Correct |
263 ms |
56400 KB |
Output is correct |
18 |
Correct |
265 ms |
56148 KB |
Output is correct |
19 |
Incorrect |
321 ms |
54352 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |