#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 300 * 1000 + 10;
struct SegTree {
ll T[(1 << 20)];
int R;
void upd(int a, ll x) {
a += R;
T[a] += x;
while (a > 1) {
a >>= 1;
T[a] += x;
}
}
ll qr(int a, int b) {
a += R; b += R;
if (a > b) return 0LL;
ll w = T[a] + (a != b ? T[b] : 0LL);
while (a/2 != b/2) {
if (a % 2 == 0) w += T[a + 1];
if (b % 2 == 1) w += T[b - 1];
a >>= 1;
b >>= 1;
}
return w;
}
void init(int n) {
R = 1;
while (R < n) R <<= 1;
for (int i = 0; i < 2 * R; ++i) T[i] = 0;
}
int go_down() {
int v = 1;
while (v < R) {
if (T[2 * v + 1] != 0) v = v*2 + 1;
else v = v*2;
}
return v - R;
}
};
vector<pair<int,int>>qrs[nax];
ll ans[nax];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
ll d;
cin >> n >> d;
vector<ll> a(n);
for (ll &x : a) cin >> x;
cin >> q;
vector<ll> demands(n);
for (int i = 1; i < n; ++i) {
demands[i] = a[i] - a[i - 1];
if (demands[i] < 0) {
demands[i] = (abs(demands[i]) - 1) / d + 1;
} else {
demands[i] = -(demands[i] / d);
}
}
for (int l,r, i = 0; i < q; ++i) {
cin >> l >> r;
l--, r--;
qrs[r].emplace_back(l, i);
}
SegTree s, lft, closed, total;
s.init(n);
lft.init(n);
closed.init(n);
total.init(n);
for (int i = 1; i < n; ++i) {
// update value i
//cerr << "i: " << i << " " << demands[i] << "\n";
if (demands[i] < 0) {
s.upd(i, -demands[i]); // I can give that many
} else {
lft.upd(i, demands[i] * i);
total.upd(i, demands[i]);
while (demands[i] > 0) {
if (s.T[1] == 0) break;
int v = s.go_down();
ll me = min(demands[i], s.qr(v,v));
s.upd(v, -me);
demands[i] -= me;
closed.upd(v, me);
lft.upd(v, -me * v);
//cerr << "segment: " << v << "->" << i << " " << me << " times\n";
}
}
for (auto [l, id] : qrs[i]) {
ll open = total.qr(l + 1, i) - closed.qr(l + 1, i);
ll res = lft.qr(l + 1, i);
ll me = a[l] / d;
//cerr << "(" << total.qr(l+1,i) << " " << closed.qr(l+1, i) << ")" << " " << res << " " << me << "\n";
if (me < open) {
ans[id] = -1;
} else {
ans[id] = res - (ll)l * open;
}
}
}
for (int i = 0; i < q; ++i) cout << ans[i] << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
40280 KB |
Output is correct |
2 |
Correct |
16 ms |
40284 KB |
Output is correct |
3 |
Correct |
15 ms |
40284 KB |
Output is correct |
4 |
Correct |
18 ms |
40640 KB |
Output is correct |
5 |
Correct |
18 ms |
40536 KB |
Output is correct |
6 |
Correct |
19 ms |
40536 KB |
Output is correct |
7 |
Correct |
17 ms |
40540 KB |
Output is correct |
8 |
Correct |
18 ms |
40540 KB |
Output is correct |
9 |
Correct |
17 ms |
40512 KB |
Output is correct |
10 |
Correct |
19 ms |
40536 KB |
Output is correct |
11 |
Correct |
18 ms |
40540 KB |
Output is correct |
12 |
Correct |
23 ms |
40540 KB |
Output is correct |
13 |
Correct |
18 ms |
40536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
249 ms |
55112 KB |
Output is correct |
2 |
Correct |
263 ms |
54356 KB |
Output is correct |
3 |
Correct |
109 ms |
47696 KB |
Output is correct |
4 |
Correct |
262 ms |
54100 KB |
Output is correct |
5 |
Correct |
232 ms |
54100 KB |
Output is correct |
6 |
Correct |
246 ms |
53848 KB |
Output is correct |
7 |
Correct |
234 ms |
53840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
51476 KB |
Output is correct |
2 |
Correct |
297 ms |
66132 KB |
Output is correct |
3 |
Correct |
341 ms |
66132 KB |
Output is correct |
4 |
Correct |
298 ms |
66336 KB |
Output is correct |
5 |
Correct |
271 ms |
66192 KB |
Output is correct |
6 |
Correct |
271 ms |
59728 KB |
Output is correct |
7 |
Correct |
239 ms |
59732 KB |
Output is correct |
8 |
Correct |
284 ms |
63124 KB |
Output is correct |
9 |
Correct |
275 ms |
63060 KB |
Output is correct |
10 |
Correct |
240 ms |
61520 KB |
Output is correct |
11 |
Correct |
231 ms |
61524 KB |
Output is correct |
12 |
Correct |
263 ms |
64596 KB |
Output is correct |
13 |
Correct |
257 ms |
64552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
199 ms |
53840 KB |
Output is correct |
2 |
Correct |
225 ms |
54932 KB |
Output is correct |
3 |
Correct |
184 ms |
49748 KB |
Output is correct |
4 |
Correct |
276 ms |
55072 KB |
Output is correct |
5 |
Correct |
251 ms |
57624 KB |
Output is correct |
6 |
Correct |
274 ms |
58452 KB |
Output is correct |
7 |
Correct |
233 ms |
56912 KB |
Output is correct |
8 |
Correct |
249 ms |
58448 KB |
Output is correct |
9 |
Correct |
242 ms |
54356 KB |
Output is correct |
10 |
Correct |
238 ms |
54176 KB |
Output is correct |
11 |
Correct |
266 ms |
55164 KB |
Output is correct |
12 |
Correct |
247 ms |
54236 KB |
Output is correct |
13 |
Correct |
263 ms |
58192 KB |
Output is correct |
14 |
Correct |
254 ms |
54096 KB |
Output is correct |
15 |
Correct |
260 ms |
58164 KB |
Output is correct |
16 |
Correct |
255 ms |
54100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
40280 KB |
Output is correct |
2 |
Correct |
16 ms |
40284 KB |
Output is correct |
3 |
Correct |
15 ms |
40284 KB |
Output is correct |
4 |
Correct |
18 ms |
40640 KB |
Output is correct |
5 |
Correct |
18 ms |
40536 KB |
Output is correct |
6 |
Correct |
19 ms |
40536 KB |
Output is correct |
7 |
Correct |
17 ms |
40540 KB |
Output is correct |
8 |
Correct |
18 ms |
40540 KB |
Output is correct |
9 |
Correct |
17 ms |
40512 KB |
Output is correct |
10 |
Correct |
19 ms |
40536 KB |
Output is correct |
11 |
Correct |
18 ms |
40540 KB |
Output is correct |
12 |
Correct |
23 ms |
40540 KB |
Output is correct |
13 |
Correct |
18 ms |
40536 KB |
Output is correct |
14 |
Correct |
249 ms |
55112 KB |
Output is correct |
15 |
Correct |
263 ms |
54356 KB |
Output is correct |
16 |
Correct |
109 ms |
47696 KB |
Output is correct |
17 |
Correct |
262 ms |
54100 KB |
Output is correct |
18 |
Correct |
232 ms |
54100 KB |
Output is correct |
19 |
Correct |
246 ms |
53848 KB |
Output is correct |
20 |
Correct |
234 ms |
53840 KB |
Output is correct |
21 |
Correct |
119 ms |
51476 KB |
Output is correct |
22 |
Correct |
297 ms |
66132 KB |
Output is correct |
23 |
Correct |
341 ms |
66132 KB |
Output is correct |
24 |
Correct |
298 ms |
66336 KB |
Output is correct |
25 |
Correct |
271 ms |
66192 KB |
Output is correct |
26 |
Correct |
271 ms |
59728 KB |
Output is correct |
27 |
Correct |
239 ms |
59732 KB |
Output is correct |
28 |
Correct |
284 ms |
63124 KB |
Output is correct |
29 |
Correct |
275 ms |
63060 KB |
Output is correct |
30 |
Correct |
240 ms |
61520 KB |
Output is correct |
31 |
Correct |
231 ms |
61524 KB |
Output is correct |
32 |
Correct |
263 ms |
64596 KB |
Output is correct |
33 |
Correct |
257 ms |
64552 KB |
Output is correct |
34 |
Correct |
199 ms |
53840 KB |
Output is correct |
35 |
Correct |
225 ms |
54932 KB |
Output is correct |
36 |
Correct |
184 ms |
49748 KB |
Output is correct |
37 |
Correct |
276 ms |
55072 KB |
Output is correct |
38 |
Correct |
251 ms |
57624 KB |
Output is correct |
39 |
Correct |
274 ms |
58452 KB |
Output is correct |
40 |
Correct |
233 ms |
56912 KB |
Output is correct |
41 |
Correct |
249 ms |
58448 KB |
Output is correct |
42 |
Correct |
242 ms |
54356 KB |
Output is correct |
43 |
Correct |
238 ms |
54176 KB |
Output is correct |
44 |
Correct |
266 ms |
55164 KB |
Output is correct |
45 |
Correct |
247 ms |
54236 KB |
Output is correct |
46 |
Correct |
263 ms |
58192 KB |
Output is correct |
47 |
Correct |
254 ms |
54096 KB |
Output is correct |
48 |
Correct |
260 ms |
58164 KB |
Output is correct |
49 |
Correct |
255 ms |
54100 KB |
Output is correct |
50 |
Correct |
293 ms |
66128 KB |
Output is correct |
51 |
Correct |
252 ms |
59732 KB |
Output is correct |
52 |
Correct |
277 ms |
63060 KB |
Output is correct |
53 |
Correct |
236 ms |
61608 KB |
Output is correct |
54 |
Correct |
266 ms |
64592 KB |
Output is correct |
55 |
Correct |
329 ms |
66072 KB |
Output is correct |
56 |
Correct |
251 ms |
61776 KB |
Output is correct |
57 |
Correct |
230 ms |
58648 KB |
Output is correct |
58 |
Correct |
225 ms |
58708 KB |
Output is correct |
59 |
Correct |
279 ms |
64124 KB |
Output is correct |
60 |
Correct |
234 ms |
61776 KB |
Output is correct |
61 |
Correct |
240 ms |
61776 KB |
Output is correct |
62 |
Correct |
243 ms |
61524 KB |
Output is correct |
63 |
Correct |
270 ms |
64336 KB |
Output is correct |
64 |
Correct |
228 ms |
61776 KB |
Output is correct |