#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long
using namespace std;
vector <ll> V;
ll n, d, q, a, b, f, s, C[300000], L[300000], P[300000], H[300000], G[300000], bl[300000][19], ps[300000][19];
struct SegTree{
ll st[1200000];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = H[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = min(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return 1e18;
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return min(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}
}ST;
int main() {
cin >> n >> d;
for (int i=0; i<n; ++i) {
cin >> C[i];
L[i] = C[i] % d;
if (i) P[i] = ((L[i]-L[i-1]+d) % d) + P[i-1];
H[i] = C[i]-P[i];
G[i] = H[i] + (i ? G[i-1] : 0);
while (!V.empty()) {
auto u = V.back();
if (H[u] >= H[i]) V.pop_back();
else break;
}
if (V.empty()) bl[i][0] = i;
else {
ps[i][0] = H[i] * (i-V.back());
bl[i][0] = V.back();
}
//cout << i << " " << bl[i][0] << " " << ps[i][0] << endl;
V.push_back(i);
}
ST.build(1, 0, n-1);
for (int j=1; j<19; ++j) {
for (int i=0; i<n; ++i) {
bl[i][j] = bl[bl[i][j-1]][j-1];
ps[i][j] = ps[i][j-1] + (bl[i][j] != bl[i][j-1] ? ps[bl[i][j-1]][j-1] : 0);
}
}
cin >> q;
while (q--) {
cin >> a >> b;
--a, --b;
if (ST.query(1, 0, n-1, a, b) < L[a]-P[a]) {
cout << "-1\n";
continue;
}
f = 0;
s = G[b] - (a ? G[a-1] : 0) + ((b-a+1) * (L[a]-P[a]));
/*cout << s << endl;
for (int i=0; i<n; ++i) {
cout << H[i] + (L[a] - P[a]) << " ";
}
cout << endl;*/
for (int j=18; j>=0; --j) {
if (bl[b][j] >= a) {
f += ps[b][j];
b = bl[b][j];
}
}
f += (b-a+1) * H[b];
cout << (s - (f + ((b-a+1) * (L[a]-P[a]))))/d << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
7 ms |
1628 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
792 ms |
115860 KB |
Output is correct |
2 |
Correct |
740 ms |
115112 KB |
Output is correct |
3 |
Correct |
457 ms |
4692 KB |
Output is correct |
4 |
Correct |
669 ms |
115028 KB |
Output is correct |
5 |
Correct |
666 ms |
114764 KB |
Output is correct |
6 |
Correct |
733 ms |
114632 KB |
Output is correct |
7 |
Correct |
720 ms |
114600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
505 ms |
8484 KB |
Output is correct |
2 |
Correct |
847 ms |
122524 KB |
Output is correct |
3 |
Correct |
811 ms |
122636 KB |
Output is correct |
4 |
Correct |
860 ms |
122448 KB |
Output is correct |
5 |
Correct |
818 ms |
122516 KB |
Output is correct |
6 |
Correct |
758 ms |
116048 KB |
Output is correct |
7 |
Correct |
802 ms |
115980 KB |
Output is correct |
8 |
Correct |
810 ms |
119380 KB |
Output is correct |
9 |
Correct |
851 ms |
119284 KB |
Output is correct |
10 |
Correct |
1174 ms |
120248 KB |
Output is correct |
11 |
Correct |
1128 ms |
120248 KB |
Output is correct |
12 |
Correct |
1054 ms |
122056 KB |
Output is correct |
13 |
Correct |
1050 ms |
122052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
726 ms |
94292 KB |
Output is correct |
2 |
Correct |
765 ms |
115800 KB |
Output is correct |
3 |
Correct |
625 ms |
30320 KB |
Output is correct |
4 |
Correct |
837 ms |
119136 KB |
Output is correct |
5 |
Correct |
864 ms |
109536 KB |
Output is correct |
6 |
Correct |
885 ms |
122384 KB |
Output is correct |
7 |
Correct |
790 ms |
95896 KB |
Output is correct |
8 |
Correct |
836 ms |
122192 KB |
Output is correct |
9 |
Correct |
714 ms |
115024 KB |
Output is correct |
10 |
Correct |
692 ms |
114768 KB |
Output is correct |
11 |
Correct |
821 ms |
119056 KB |
Output is correct |
12 |
Correct |
779 ms |
118328 KB |
Output is correct |
13 |
Correct |
831 ms |
122064 KB |
Output is correct |
14 |
Correct |
722 ms |
118100 KB |
Output is correct |
15 |
Correct |
837 ms |
122096 KB |
Output is correct |
16 |
Correct |
729 ms |
118168 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 |
348 KB |
Output is correct |
4 |
Incorrect |
7 ms |
1628 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |