#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int mod = 998244353, N = 300005;
struct Seg {
int l, r, m;
ll lz, sum;
Seg* ch[2];
Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
if (r - l > 1) {
ch[0] = new Seg(l, m);
ch[1] = new Seg(m, r);
}
}
void pull() {
sum = ch[0]->sum + ch[1]->sum;
}
void give(ll x) {
lz += x, sum += x * (r - l);
}
void push() {
if (!lz) {
return;
}
ch[0]->give(lz), ch[1]->give(lz), lz = 0;
}
void add(int a, int b, ll v) {
if (a <= l && r <= b) {
give(v);
} else {
push();
if (a < m) {
ch[0]->add(a, b, v);
}
if (m < b) {
ch[1]->add(a, b, v);
}
pull();
}
}
ll query(int a, int b) {
if (a <= l && r <= b) {
return sum;
}
push();
ll ans = 0;
if (a < m) {
ans += ch[0]->query(a, b);
}
if (m < b) {
ans += ch[1]->query(a, b);
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
ll d;
cin >> n >> d;
vector <ll> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
b[i] = a[i] % d, a[i] /= d;
}
// b[i] > b[i + 1] -> a[i] + add[i] <= a[i + 1] + add[i + 1]
vector <int> add(n);
for (int i = 1; i < n; ++i) if (b[i - 1] > b[i]) {
add[i - 1]++;
}
for (int i = n - 2; i >= 0; --i) {
add[i] += add[i + 1];
}
vector <ll> pre_a(n + 1);
for (int i = 0; i < n; ++i) {
a[i] += add[i];
pre_a[i + 1] = pre_a[i] + a[i];
}
int q;
cin >> q;
vector <vector <pii>> queries(n + 1);
for (int i = 0, l, r; i < q; ++i) {
cin >> l >> r, --l, --r;
queries[r].emplace_back(l, i);
}
Seg root(0, n);
vector <array <ll, 3>> stk;
vector <ll> ans(q);
for (int i = 0; i < n; ++i) {
// push i
int lstl = i;
while (!stk.empty() && stk.back()[2] >= a[i]) {
root.add(stk.back()[0], stk.back()[1], -stk.back()[2]);
lstl = stk.back()[0];
stk.pop_back();
}
root.add(lstl, i + 1, a[i]);
stk.pb({lstl, i + 1, a[i]});
// handle query
for (auto [l, id] : queries[i]) {
ll suma = root.query(l, i + 1);
ll lst = root.query(l, l + 1);
if (lst - add[l] < 0) {
ans[id] = -1;
} else {
ans[id] = (pre_a[i + 1] - pre_a[l]) - suma;
}
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}
Compilation message
Main.cpp: In constructor 'Seg::Seg(int, int)':
Main.cpp:13:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
4 ms |
1112 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
3 ms |
976 KB |
Output is correct |
9 |
Correct |
3 ms |
976 KB |
Output is correct |
10 |
Correct |
3 ms |
1116 KB |
Output is correct |
11 |
Correct |
3 ms |
1116 KB |
Output is correct |
12 |
Correct |
4 ms |
1112 KB |
Output is correct |
13 |
Correct |
3 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
470 ms |
67620 KB |
Output is correct |
2 |
Correct |
460 ms |
67096 KB |
Output is correct |
3 |
Correct |
109 ms |
10404 KB |
Output is correct |
4 |
Correct |
420 ms |
66776 KB |
Output is correct |
5 |
Correct |
440 ms |
66816 KB |
Output is correct |
6 |
Correct |
468 ms |
66584 KB |
Output is correct |
7 |
Correct |
407 ms |
66676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
14260 KB |
Output is correct |
2 |
Correct |
457 ms |
74576 KB |
Output is correct |
3 |
Correct |
477 ms |
74556 KB |
Output is correct |
4 |
Correct |
462 ms |
74420 KB |
Output is correct |
5 |
Correct |
485 ms |
74396 KB |
Output is correct |
6 |
Correct |
455 ms |
68100 KB |
Output is correct |
7 |
Correct |
439 ms |
68176 KB |
Output is correct |
8 |
Correct |
465 ms |
71368 KB |
Output is correct |
9 |
Correct |
470 ms |
71192 KB |
Output is correct |
10 |
Correct |
438 ms |
82896 KB |
Output is correct |
11 |
Correct |
488 ms |
82964 KB |
Output is correct |
12 |
Correct |
455 ms |
75968 KB |
Output is correct |
13 |
Correct |
463 ms |
75888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
398 ms |
58312 KB |
Output is correct |
2 |
Correct |
429 ms |
67924 KB |
Output is correct |
3 |
Correct |
213 ms |
24476 KB |
Output is correct |
4 |
Correct |
462 ms |
71076 KB |
Output is correct |
5 |
Correct |
451 ms |
67152 KB |
Output is correct |
6 |
Correct |
472 ms |
74400 KB |
Output is correct |
7 |
Correct |
416 ms |
61628 KB |
Output is correct |
8 |
Correct |
443 ms |
74324 KB |
Output is correct |
9 |
Correct |
481 ms |
67096 KB |
Output is correct |
10 |
Correct |
413 ms |
66900 KB |
Output is correct |
11 |
Correct |
438 ms |
70996 KB |
Output is correct |
12 |
Correct |
467 ms |
70344 KB |
Output is correct |
13 |
Correct |
460 ms |
74136 KB |
Output is correct |
14 |
Correct |
430 ms |
70124 KB |
Output is correct |
15 |
Correct |
464 ms |
74148 KB |
Output is correct |
16 |
Correct |
450 ms |
70040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
1116 KB |
Output is correct |
5 |
Correct |
4 ms |
1112 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
3 ms |
976 KB |
Output is correct |
9 |
Correct |
3 ms |
976 KB |
Output is correct |
10 |
Correct |
3 ms |
1116 KB |
Output is correct |
11 |
Correct |
3 ms |
1116 KB |
Output is correct |
12 |
Correct |
4 ms |
1112 KB |
Output is correct |
13 |
Correct |
3 ms |
1116 KB |
Output is correct |
14 |
Correct |
470 ms |
67620 KB |
Output is correct |
15 |
Correct |
460 ms |
67096 KB |
Output is correct |
16 |
Correct |
109 ms |
10404 KB |
Output is correct |
17 |
Correct |
420 ms |
66776 KB |
Output is correct |
18 |
Correct |
440 ms |
66816 KB |
Output is correct |
19 |
Correct |
468 ms |
66584 KB |
Output is correct |
20 |
Correct |
407 ms |
66676 KB |
Output is correct |
21 |
Correct |
114 ms |
14260 KB |
Output is correct |
22 |
Correct |
457 ms |
74576 KB |
Output is correct |
23 |
Correct |
477 ms |
74556 KB |
Output is correct |
24 |
Correct |
462 ms |
74420 KB |
Output is correct |
25 |
Correct |
485 ms |
74396 KB |
Output is correct |
26 |
Correct |
455 ms |
68100 KB |
Output is correct |
27 |
Correct |
439 ms |
68176 KB |
Output is correct |
28 |
Correct |
465 ms |
71368 KB |
Output is correct |
29 |
Correct |
470 ms |
71192 KB |
Output is correct |
30 |
Correct |
438 ms |
82896 KB |
Output is correct |
31 |
Correct |
488 ms |
82964 KB |
Output is correct |
32 |
Correct |
455 ms |
75968 KB |
Output is correct |
33 |
Correct |
463 ms |
75888 KB |
Output is correct |
34 |
Correct |
398 ms |
58312 KB |
Output is correct |
35 |
Correct |
429 ms |
67924 KB |
Output is correct |
36 |
Correct |
213 ms |
24476 KB |
Output is correct |
37 |
Correct |
462 ms |
71076 KB |
Output is correct |
38 |
Correct |
451 ms |
67152 KB |
Output is correct |
39 |
Correct |
472 ms |
74400 KB |
Output is correct |
40 |
Correct |
416 ms |
61628 KB |
Output is correct |
41 |
Correct |
443 ms |
74324 KB |
Output is correct |
42 |
Correct |
481 ms |
67096 KB |
Output is correct |
43 |
Correct |
413 ms |
66900 KB |
Output is correct |
44 |
Correct |
438 ms |
70996 KB |
Output is correct |
45 |
Correct |
467 ms |
70344 KB |
Output is correct |
46 |
Correct |
460 ms |
74136 KB |
Output is correct |
47 |
Correct |
430 ms |
70124 KB |
Output is correct |
48 |
Correct |
464 ms |
74148 KB |
Output is correct |
49 |
Correct |
450 ms |
70040 KB |
Output is correct |
50 |
Correct |
448 ms |
74400 KB |
Output is correct |
51 |
Correct |
441 ms |
68012 KB |
Output is correct |
52 |
Correct |
469 ms |
71348 KB |
Output is correct |
53 |
Correct |
426 ms |
81280 KB |
Output is correct |
54 |
Correct |
494 ms |
75980 KB |
Output is correct |
55 |
Correct |
479 ms |
74508 KB |
Output is correct |
56 |
Correct |
473 ms |
70056 KB |
Output is correct |
57 |
Correct |
434 ms |
67020 KB |
Output is correct |
58 |
Correct |
429 ms |
67088 KB |
Output is correct |
59 |
Correct |
464 ms |
72384 KB |
Output is correct |
60 |
Correct |
449 ms |
70060 KB |
Output is correct |
61 |
Correct |
415 ms |
82872 KB |
Output is correct |
62 |
Correct |
434 ms |
69640 KB |
Output is correct |
63 |
Correct |
469 ms |
75744 KB |
Output is correct |
64 |
Correct |
440 ms |
70044 KB |
Output is correct |