# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
984788 |
2024-05-17T05:38:20 Z |
pavement |
Fish 3 (JOI24_fish3) |
C++17 |
|
551 ms |
82700 KB |
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
#define pb push_back
#define eb emplace_back
int N, Q, suf[300005];
ll D, C[300005], ans[300005], pre[300005];
vector<int> limiters;
vector<ii> vec[300005];
multiset<int> inv;
struct node {
node *left, *right;
int S, E;
ll val, pv;
bool ip;
node(int _s, int _e) : S(_s), E(_e), val(0), ip(0){
if (S == E) {
return;
}
int M = (S + E) / 2;
left = new node(S, M);
right = new node(M + 1, E);
}
void prop() {
if (!ip) {
return;
}
left->val = (left->E - left->S + 1) * pv;
right->val = (right->E - right->S + 1) * pv;
left->pv = right->pv = pv;
left->ip = right->ip = 1;
ip = 0;
}
void upd(int l, int r, ll v) {
if (l > E || r < S) {
return;
}
if (l <= S && E <= r) {
val = (E - S + 1) * v;
pv = v;
ip = 1;
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
val = left->val + right->val;
}
ll qry(int l, int r) {
if (l > E || r < S) {
return 0;
}
if (l <= S && E <= r) {
return val;
}
prop();
return left->qry(l, r) + right->qry(l, r);
}
} *root;
int find_inv(int l, int r) {
int lo = l, hi = r, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (C[r] / D - (suf[mid] - suf[r]) < 0) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> D;
for (int i = 1; i <= N; i++) {
cin >> C[i];
}
for (int i = N - 1; i >= 1; i--) {
suf[i] = suf[i + 1] + (C[i + 1] % D < C[i] % D);
}
for (int i = 1; i <= N; i++) {
pre[i] = pre[i - 1] + (C[i] / D + suf[i]);
}
cin >> Q;
for (int i = 1, L, R; i <= Q; i++) {
cin >> L >> R;
vec[R].eb(L, i);
}
root = new node(1, N);
for (int R = 1; R <= N; R++) {
while (!limiters.empty()) {
int x = limiters.back();
auto a = (C[R] / D) - (suf[x + 1] - suf[R]);
auto b = C[x + 1] % D;
if (a * D + b <= C[x]) {
limiters.pop_back();
int y = (limiters.empty() ? 0 : limiters.back()) + 1;
inv.erase(inv.find(find_inv(y, x)));
} else {
break;
}
}
int y = (limiters.empty() ? 0 : limiters.back()) + 1;
limiters.pb(R);
root->upd(y, R, C[R] / D + suf[R]);
int tmp = find_inv(y, R);
inv.insert(tmp);
for (auto [L, idx] : vec[R]) {
if (*inv.rbegin() >= L) {
ans[idx] = -1;
} else {
ans[idx] = pre[R] - pre[L - 1] - root->qry(L, R);
}
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
6 ms |
15452 KB |
Output is correct |
5 |
Correct |
5 ms |
15452 KB |
Output is correct |
6 |
Correct |
5 ms |
15196 KB |
Output is correct |
7 |
Correct |
4 ms |
15192 KB |
Output is correct |
8 |
Correct |
5 ms |
15448 KB |
Output is correct |
9 |
Correct |
4 ms |
15452 KB |
Output is correct |
10 |
Correct |
5 ms |
15496 KB |
Output is correct |
11 |
Correct |
5 ms |
15452 KB |
Output is correct |
12 |
Correct |
5 ms |
15452 KB |
Output is correct |
13 |
Correct |
5 ms |
15568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
403 ms |
65352 KB |
Output is correct |
2 |
Correct |
381 ms |
64728 KB |
Output is correct |
3 |
Correct |
54 ms |
22396 KB |
Output is correct |
4 |
Correct |
199 ms |
64544 KB |
Output is correct |
5 |
Correct |
217 ms |
64460 KB |
Output is correct |
6 |
Correct |
285 ms |
64208 KB |
Output is correct |
7 |
Correct |
306 ms |
64404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
26252 KB |
Output is correct |
2 |
Correct |
462 ms |
72040 KB |
Output is correct |
3 |
Correct |
466 ms |
72160 KB |
Output is correct |
4 |
Correct |
487 ms |
72532 KB |
Output is correct |
5 |
Correct |
436 ms |
72268 KB |
Output is correct |
6 |
Correct |
387 ms |
65768 KB |
Output is correct |
7 |
Correct |
383 ms |
65768 KB |
Output is correct |
8 |
Correct |
449 ms |
69148 KB |
Output is correct |
9 |
Correct |
430 ms |
69200 KB |
Output is correct |
10 |
Correct |
446 ms |
82652 KB |
Output is correct |
11 |
Correct |
471 ms |
82584 KB |
Output is correct |
12 |
Correct |
462 ms |
76616 KB |
Output is correct |
13 |
Correct |
461 ms |
76744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
58196 KB |
Output is correct |
2 |
Correct |
415 ms |
65616 KB |
Output is correct |
3 |
Correct |
191 ms |
33188 KB |
Output is correct |
4 |
Correct |
429 ms |
68588 KB |
Output is correct |
5 |
Correct |
429 ms |
66500 KB |
Output is correct |
6 |
Correct |
486 ms |
71900 KB |
Output is correct |
7 |
Correct |
408 ms |
62164 KB |
Output is correct |
8 |
Correct |
526 ms |
71776 KB |
Output is correct |
9 |
Correct |
271 ms |
64596 KB |
Output is correct |
10 |
Correct |
299 ms |
64400 KB |
Output is correct |
11 |
Correct |
435 ms |
68688 KB |
Output is correct |
12 |
Correct |
331 ms |
67708 KB |
Output is correct |
13 |
Correct |
456 ms |
71744 KB |
Output is correct |
14 |
Correct |
216 ms |
67644 KB |
Output is correct |
15 |
Correct |
472 ms |
71620 KB |
Output is correct |
16 |
Correct |
226 ms |
67588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
6 ms |
15452 KB |
Output is correct |
5 |
Correct |
5 ms |
15452 KB |
Output is correct |
6 |
Correct |
5 ms |
15196 KB |
Output is correct |
7 |
Correct |
4 ms |
15192 KB |
Output is correct |
8 |
Correct |
5 ms |
15448 KB |
Output is correct |
9 |
Correct |
4 ms |
15452 KB |
Output is correct |
10 |
Correct |
5 ms |
15496 KB |
Output is correct |
11 |
Correct |
5 ms |
15452 KB |
Output is correct |
12 |
Correct |
5 ms |
15452 KB |
Output is correct |
13 |
Correct |
5 ms |
15568 KB |
Output is correct |
14 |
Correct |
403 ms |
65352 KB |
Output is correct |
15 |
Correct |
381 ms |
64728 KB |
Output is correct |
16 |
Correct |
54 ms |
22396 KB |
Output is correct |
17 |
Correct |
199 ms |
64544 KB |
Output is correct |
18 |
Correct |
217 ms |
64460 KB |
Output is correct |
19 |
Correct |
285 ms |
64208 KB |
Output is correct |
20 |
Correct |
306 ms |
64404 KB |
Output is correct |
21 |
Correct |
109 ms |
26252 KB |
Output is correct |
22 |
Correct |
462 ms |
72040 KB |
Output is correct |
23 |
Correct |
466 ms |
72160 KB |
Output is correct |
24 |
Correct |
487 ms |
72532 KB |
Output is correct |
25 |
Correct |
436 ms |
72268 KB |
Output is correct |
26 |
Correct |
387 ms |
65768 KB |
Output is correct |
27 |
Correct |
383 ms |
65768 KB |
Output is correct |
28 |
Correct |
449 ms |
69148 KB |
Output is correct |
29 |
Correct |
430 ms |
69200 KB |
Output is correct |
30 |
Correct |
446 ms |
82652 KB |
Output is correct |
31 |
Correct |
471 ms |
82584 KB |
Output is correct |
32 |
Correct |
462 ms |
76616 KB |
Output is correct |
33 |
Correct |
461 ms |
76744 KB |
Output is correct |
34 |
Correct |
362 ms |
58196 KB |
Output is correct |
35 |
Correct |
415 ms |
65616 KB |
Output is correct |
36 |
Correct |
191 ms |
33188 KB |
Output is correct |
37 |
Correct |
429 ms |
68588 KB |
Output is correct |
38 |
Correct |
429 ms |
66500 KB |
Output is correct |
39 |
Correct |
486 ms |
71900 KB |
Output is correct |
40 |
Correct |
408 ms |
62164 KB |
Output is correct |
41 |
Correct |
526 ms |
71776 KB |
Output is correct |
42 |
Correct |
271 ms |
64596 KB |
Output is correct |
43 |
Correct |
299 ms |
64400 KB |
Output is correct |
44 |
Correct |
435 ms |
68688 KB |
Output is correct |
45 |
Correct |
331 ms |
67708 KB |
Output is correct |
46 |
Correct |
456 ms |
71744 KB |
Output is correct |
47 |
Correct |
216 ms |
67644 KB |
Output is correct |
48 |
Correct |
472 ms |
71620 KB |
Output is correct |
49 |
Correct |
226 ms |
67588 KB |
Output is correct |
50 |
Correct |
498 ms |
71936 KB |
Output is correct |
51 |
Correct |
501 ms |
65688 KB |
Output is correct |
52 |
Correct |
467 ms |
68896 KB |
Output is correct |
53 |
Correct |
504 ms |
82700 KB |
Output is correct |
54 |
Correct |
547 ms |
76584 KB |
Output is correct |
55 |
Correct |
517 ms |
71860 KB |
Output is correct |
56 |
Correct |
236 ms |
67412 KB |
Output is correct |
57 |
Correct |
220 ms |
64380 KB |
Output is correct |
58 |
Correct |
249 ms |
64452 KB |
Output is correct |
59 |
Correct |
427 ms |
69708 KB |
Output is correct |
60 |
Correct |
263 ms |
67764 KB |
Output is correct |
61 |
Correct |
551 ms |
82460 KB |
Output is correct |
62 |
Correct |
481 ms |
82404 KB |
Output is correct |
63 |
Correct |
539 ms |
76424 KB |
Output is correct |
64 |
Correct |
250 ms |
67396 KB |
Output is correct |