#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct node {
int sum, sz, mx;
};
struct segtree {
int size = 1;
vector<node> seg;
vector<int> lazy;
void init(int n) {
while (size < n) size *= 2;
seg.assign(2 * size + 1, (node) {0, 0, 0});
lazy.assign(2 * size + 1, -1);
}
void pull(int id) {
seg[id].sum = seg[id * 2].sum + seg[id * 2 + 1].sum;
seg[id].sz = seg[id * 2].sz + seg[id * 2 + 1].sz;
seg[id].mx = max(seg[id * 2].mx, seg[id * 2 + 1].mx);
}
void build(int l, int r, int id) {
if (l == r) {
seg[id].sz = 1;
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2);
build(mid + 1, r, id * 2 + 1);
pull(id);
}
void push(int id) {
if (lazy[id] != -1) {
seg[id].sum = lazy[id] * seg[id].sz;
seg[id].mx = lazy[id];
}
if (id < size) for (int i = 0; i < 2; i++) if (lazy[id] != -1) lazy[id * 2 + i] = lazy[id];
lazy[id] = -1;
}
void update(int ql, int qr, int val, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[id] = val;
push(id);
return;
}
int mid = (l + r) / 2;
update(ql, qr, val, l, mid, id * 2) ;
update(ql, qr, val, mid + 1, r, id * 2 + 1);
pull(id);
}
int query(int ql, int qr, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return seg[id].sum;
int mid = (l + r) / 2;
return query(ql, qr, l, mid, id * 2) + query(ql, qr, mid + 1, r, id * 2 + 1);
}
int find(int ql, int qr, int x, int l, int r, int id) {
push(id);
// cout << l << ' ' << r << ' ' << x << ' ' << seg[id].mx << '\n';
if (qr < l || r < ql) return -1;
if (l == r && seg[id].mx > x) return l;
else if (l == r) return -1;
int mid = (l + r) / 2;
int ans = -1;
if (seg[id * 2].mx > x) ans = find(ql, qr, x, l, mid, id * 2);
if (ans == -1) return find(ql, qr, x, mid + 1, r, id * 2 + 1);
return ans;
}
} st;
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q;
cin >> n >> k;
vector<int> c(n+1), ac(n+1, 0), a(n+1, 0), d(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> c[i];
ac[i] = c[i];
}
for (int i = n - 1; i >= 1; i--) {
if (ac[i] > ac[i + 1]) {
int diff = ac[i] - ac[i + 1];
diff = (diff + k - 1) / k;
a[i] += diff;
ac[i] -= diff * k;
d[i] = diff;
}
}
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
st.init(n + 1);
st.build(1, n, 1);
vector<vector<pair<int, int>>> qry(n+1);
cin >> q;
vector<int> ans(q+1, 0);
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
qry[r].push_back({l, i});
}
// for (int i = 1; i <= n; i++) cout << d[i] << ' ';
// cout << '\n';
for (int r = 1; r <= n; r++) {
if (r > 1) {
int id = st.find(1, r - 1, d[r], 1, n, 1);
// cout << "id: " << id << '\n';
if (id == -1) id = r;
if (id <= r) {
// cout << "update: " << id << ' ' << r << ' ' << d[r] << '\n';
st.update(id, r, d[r], 1, n, 1);
}
} else {
// cout << "update: " << 1 << " " << 1 << " " << d[1] << "\n";
st.update(1, 1, d[1], 1, n, 1);
}
for (auto& [l, idx] : qry[r]) {
int v = st.query(l, l, 1, n, 1);
if (ac[l] + k * v < 0) ans[idx] = -1;
else ans[idx] = a[r] - a[l - 1] - st.query(l, r, 1, n, 1);
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
// -5 -7 -6 -3 -4 -5 0
// -3 -3 -4 -5
// then take sum of negative "caused" by back element
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
368 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
788 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
3 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
860 KB |
Output is correct |
11 |
Correct |
3 ms |
860 KB |
Output is correct |
12 |
Correct |
4 ms |
860 KB |
Output is correct |
13 |
Correct |
3 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
461 ms |
61720 KB |
Output is correct |
2 |
Correct |
444 ms |
60956 KB |
Output is correct |
3 |
Correct |
97 ms |
11768 KB |
Output is correct |
4 |
Correct |
375 ms |
60768 KB |
Output is correct |
5 |
Correct |
374 ms |
60692 KB |
Output is correct |
6 |
Correct |
369 ms |
60500 KB |
Output is correct |
7 |
Correct |
357 ms |
60560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
153 ms |
15696 KB |
Output is correct |
2 |
Correct |
469 ms |
65104 KB |
Output is correct |
3 |
Correct |
493 ms |
65152 KB |
Output is correct |
4 |
Correct |
483 ms |
65252 KB |
Output is correct |
5 |
Correct |
514 ms |
65152 KB |
Output is correct |
6 |
Correct |
495 ms |
61968 KB |
Output is correct |
7 |
Correct |
449 ms |
61976 KB |
Output is correct |
8 |
Correct |
481 ms |
61968 KB |
Output is correct |
9 |
Correct |
568 ms |
62036 KB |
Output is correct |
10 |
Correct |
433 ms |
60496 KB |
Output is correct |
11 |
Correct |
480 ms |
60496 KB |
Output is correct |
12 |
Correct |
470 ms |
63500 KB |
Output is correct |
13 |
Correct |
472 ms |
63572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
389 ms |
42324 KB |
Output is correct |
2 |
Correct |
457 ms |
61716 KB |
Output is correct |
3 |
Correct |
234 ms |
23888 KB |
Output is correct |
4 |
Correct |
490 ms |
61836 KB |
Output is correct |
5 |
Correct |
534 ms |
63012 KB |
Output is correct |
6 |
Correct |
545 ms |
64848 KB |
Output is correct |
7 |
Correct |
463 ms |
44972 KB |
Output is correct |
8 |
Correct |
583 ms |
65008 KB |
Output is correct |
9 |
Correct |
374 ms |
61012 KB |
Output is correct |
10 |
Correct |
338 ms |
60792 KB |
Output is correct |
11 |
Correct |
497 ms |
61768 KB |
Output is correct |
12 |
Correct |
395 ms |
61012 KB |
Output is correct |
13 |
Correct |
559 ms |
64848 KB |
Output is correct |
14 |
Correct |
441 ms |
61008 KB |
Output is correct |
15 |
Correct |
606 ms |
64952 KB |
Output is correct |
16 |
Correct |
424 ms |
60692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
368 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
788 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
3 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
860 KB |
Output is correct |
11 |
Correct |
3 ms |
860 KB |
Output is correct |
12 |
Correct |
4 ms |
860 KB |
Output is correct |
13 |
Correct |
3 ms |
860 KB |
Output is correct |
14 |
Correct |
461 ms |
61720 KB |
Output is correct |
15 |
Correct |
444 ms |
60956 KB |
Output is correct |
16 |
Correct |
97 ms |
11768 KB |
Output is correct |
17 |
Correct |
375 ms |
60768 KB |
Output is correct |
18 |
Correct |
374 ms |
60692 KB |
Output is correct |
19 |
Correct |
369 ms |
60500 KB |
Output is correct |
20 |
Correct |
357 ms |
60560 KB |
Output is correct |
21 |
Correct |
153 ms |
15696 KB |
Output is correct |
22 |
Correct |
469 ms |
65104 KB |
Output is correct |
23 |
Correct |
493 ms |
65152 KB |
Output is correct |
24 |
Correct |
483 ms |
65252 KB |
Output is correct |
25 |
Correct |
514 ms |
65152 KB |
Output is correct |
26 |
Correct |
495 ms |
61968 KB |
Output is correct |
27 |
Correct |
449 ms |
61976 KB |
Output is correct |
28 |
Correct |
481 ms |
61968 KB |
Output is correct |
29 |
Correct |
568 ms |
62036 KB |
Output is correct |
30 |
Correct |
433 ms |
60496 KB |
Output is correct |
31 |
Correct |
480 ms |
60496 KB |
Output is correct |
32 |
Correct |
470 ms |
63500 KB |
Output is correct |
33 |
Correct |
472 ms |
63572 KB |
Output is correct |
34 |
Correct |
389 ms |
42324 KB |
Output is correct |
35 |
Correct |
457 ms |
61716 KB |
Output is correct |
36 |
Correct |
234 ms |
23888 KB |
Output is correct |
37 |
Correct |
490 ms |
61836 KB |
Output is correct |
38 |
Correct |
534 ms |
63012 KB |
Output is correct |
39 |
Correct |
545 ms |
64848 KB |
Output is correct |
40 |
Correct |
463 ms |
44972 KB |
Output is correct |
41 |
Correct |
583 ms |
65008 KB |
Output is correct |
42 |
Correct |
374 ms |
61012 KB |
Output is correct |
43 |
Correct |
338 ms |
60792 KB |
Output is correct |
44 |
Correct |
497 ms |
61768 KB |
Output is correct |
45 |
Correct |
395 ms |
61012 KB |
Output is correct |
46 |
Correct |
559 ms |
64848 KB |
Output is correct |
47 |
Correct |
441 ms |
61008 KB |
Output is correct |
48 |
Correct |
606 ms |
64952 KB |
Output is correct |
49 |
Correct |
424 ms |
60692 KB |
Output is correct |
50 |
Correct |
492 ms |
65260 KB |
Output is correct |
51 |
Correct |
473 ms |
61976 KB |
Output is correct |
52 |
Correct |
477 ms |
61976 KB |
Output is correct |
53 |
Correct |
443 ms |
60500 KB |
Output is correct |
54 |
Correct |
480 ms |
63516 KB |
Output is correct |
55 |
Correct |
500 ms |
65056 KB |
Output is correct |
56 |
Correct |
383 ms |
60756 KB |
Output is correct |
57 |
Correct |
387 ms |
60952 KB |
Output is correct |
58 |
Correct |
383 ms |
60684 KB |
Output is correct |
59 |
Correct |
509 ms |
63060 KB |
Output is correct |
60 |
Correct |
389 ms |
60652 KB |
Output is correct |
61 |
Correct |
423 ms |
60500 KB |
Output is correct |
62 |
Correct |
458 ms |
60448 KB |
Output is correct |
63 |
Correct |
458 ms |
63376 KB |
Output is correct |
64 |
Correct |
436 ms |
60752 KB |
Output is correct |