#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010, INF = 1e18;
struct mat {
int a[4][4];
mat() {
a[1][2] = a[1][3] = a[2][1] = a[2][3] = a[3][1] = a[3][2] = 0;
a[1][1] = a[2][2] = a[3][3] = 1;
}
mat operator*(const mat &m) const {
mat ans;
//// ans.a[1][1] = a[1][1] * m.a[1][1] + a[1][2] * m.a[2][1] + a[1][3] * m.a[3][1];
ans.a[1][1] = a[1][1] * m.a[1][1];
//// ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2] * m.a[2][2] + a[1][3] * m.a[3][2];
ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2];
//// ans.a[1][3] = a[1][1] * m.a[1][3] + a[1][2] * m.a[2][3] + a[1][3] * m.a[3][3];
//// ans.a[2][1] = a[2][1] * m.a[1][1] + a[2][2] * m.a[2][1] + a[2][3] * m.a[3][1];
//// ans.a[2][2] = a[2][1] * m.a[1][2] + a[2][2] * m.a[2][2] + a[2][3] * m.a[3][2];
//// ans.a[2][3] = a[2][1] * m.a[1][3] + a[2][2] * m.a[2][3] + a[2][3] * m.a[3][3];
ans.a[1][3] = 0ll;
ans.a[2][1] = 0ll;
ans.a[2][2] = 1ll;
ans.a[2][3] = 0ll;
ans.a[3][1] = a[3][1] * m.a[1][1] + a[3][3] * m.a[3][1];
ans.a[3][2] = a[3][1] * m.a[1][2] + a[3][2] + a[3][3] * m.a[3][2];
// ans.a[3][3] = a[3][2] * m.a[2][3] + a[3][3] * m.a[3][3];
ans.a[3][3] = 1ll;
return ans;
}
};
struct SegT {
mat t[N << 2];
bool vis[N << 2];
static inline int ls(int u) { return u << 1; }
static inline int rs(int u) { return u << 1 | 1; }
inline void pushdown(int u) {
if (vis[u]) {
t[ls(u)] = t[ls(u)] * t[u];
t[rs(u)] = t[rs(u)] * t[u];
t[u].a[1][2] = t[u].a[1][3] = t[u].a[2][1] = t[u].a[2][3] = t[u].a[3][1] = t[u].a[3][2] = 0;
t[u].a[1][1] = t[u].a[2][2] = t[u].a[3][3] = 1;
vis[u] = 0;
vis[ls(u)] = vis[rs(u)] = 1;
}
return;
}
void update(const int l, const int r, const int ql, const int qr, const int u, const mat &x) {
if (ql <= l && qr >= r) {
t[u] = t[u] * x;
vis[u] = 1;
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
// cout << '\n';
// }
return;
}
int mid((l + r) >> 1);
pushdown(u);
if (ql <= mid)update(l, mid, ql, qr, ls(u), x);
if (qr > mid)update(mid + 1, r, ql, qr, rs(u), x);
return;
}
int query(const int l, const int r, const int u, const int pos) {
// if (l == r) {
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
// cout << '\n';
// }
// return t[u];
// }
if (l == r) {
return u;
}
pushdown(u);
int mid((l + r) >> 1);
if (pos <= mid)return query(l, mid, ls(u), pos);
else return query(mid + 1, r, rs(u), pos);
}
};
SegT T;
int n, D, C[N], q, ans[N];
vector<pair<int, int>> qlist[N];
int check(int pos) {
mat nw;
nw = T.t[T.query(1, n, 1, pos)];
return INF * nw.a[1][1] + nw.a[3][1];
}
void work() {
for (int i = 1; i <= n; i++) {
int l(1), r(i), now(C[i] / D);
if (C[i] % D > C[i - 1] % D && i > 1) {
mat tmp;
tmp.a[3][1] = -1;
T.update(1, n, 1, i - 1, 1, tmp);
}
while (l < r) {
int mid((l + r) >> 1);
if (check(mid) >= now)r = mid;
else l = mid + 1;
}
if (l > 1) {
mat tmp;
tmp.a[1][2] = -1ll;
tmp.a[3][2] = now;
T.update(1, n, 1, l - 1, 1, tmp);
}
{
mat tmp;
tmp.a[1][1] = 0;
tmp.a[3][1] = now;
T.update(1, n, l, i, 1, tmp);
}
for (auto x: qlist[i]) {
mat tmp = T.t[T.query(1, n, 1, x.first)];
if (INF * tmp.a[1][1] + tmp.a[3][1] >= 0)
ans[x.second] = INF * tmp.a[1][2] + tmp.a[3][2];
else ans[x.second] = -1ll;
}
// for (int j = 1; j <= i; j++)
// cout << check(j) << ' ';
// cout << '\n';
}
return;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen("test.in", "r", stdin);
cin >> n >> D;
// cout<<clock()<<'\n';
for (int i = 1; i <= n; i++)cin >> C[n + 1 - i];
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
swap(l, r);
l = n + 1 - l;
r = n + 1 - r;
qlist[r].push_back({l, i});
}
work();
// for (int k = 1; k <= 5; k++) {
// int now = T.query(1, n, 1, k);
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++) {
// cout << T.t[now].a[i][j] << " ";
// }
// cout << '\n';
// }
// }
for (int i = 1; i <= q; i++)cout << ans[i] << '\n';
// cout<<clock()<<'\n';
return 0;
}
/*
* 6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
159064 KB |
Output is correct |
2 |
Correct |
54 ms |
159060 KB |
Output is correct |
3 |
Correct |
61 ms |
159056 KB |
Output is correct |
4 |
Correct |
62 ms |
159256 KB |
Output is correct |
5 |
Correct |
68 ms |
159316 KB |
Output is correct |
6 |
Correct |
56 ms |
159324 KB |
Output is correct |
7 |
Correct |
63 ms |
159060 KB |
Output is correct |
8 |
Correct |
58 ms |
159060 KB |
Output is correct |
9 |
Correct |
67 ms |
159064 KB |
Output is correct |
10 |
Correct |
56 ms |
159312 KB |
Output is correct |
11 |
Correct |
74 ms |
159168 KB |
Output is correct |
12 |
Correct |
64 ms |
159060 KB |
Output is correct |
13 |
Correct |
57 ms |
159176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1464 ms |
177612 KB |
Output is correct |
2 |
Correct |
1194 ms |
177008 KB |
Output is correct |
3 |
Correct |
152 ms |
172940 KB |
Output is correct |
4 |
Correct |
1294 ms |
176600 KB |
Output is correct |
5 |
Correct |
1325 ms |
176536 KB |
Output is correct |
6 |
Correct |
1295 ms |
176536 KB |
Output is correct |
7 |
Correct |
1185 ms |
176536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
176620 KB |
Output is correct |
2 |
Correct |
1328 ms |
184296 KB |
Output is correct |
3 |
Correct |
1302 ms |
184148 KB |
Output is correct |
4 |
Correct |
1325 ms |
184396 KB |
Output is correct |
5 |
Correct |
1383 ms |
184396 KB |
Output is correct |
6 |
Correct |
1354 ms |
177724 KB |
Output is correct |
7 |
Correct |
1309 ms |
177916 KB |
Output is correct |
8 |
Correct |
1401 ms |
181104 KB |
Output is correct |
9 |
Correct |
1301 ms |
181072 KB |
Output is correct |
10 |
Correct |
1152 ms |
179620 KB |
Output is correct |
11 |
Correct |
1138 ms |
179676 KB |
Output is correct |
12 |
Correct |
1316 ms |
182536 KB |
Output is correct |
13 |
Correct |
1316 ms |
182652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1043 ms |
176976 KB |
Output is correct |
2 |
Correct |
1244 ms |
177652 KB |
Output is correct |
3 |
Correct |
378 ms |
175700 KB |
Output is correct |
4 |
Correct |
1255 ms |
180792 KB |
Output is correct |
5 |
Correct |
1219 ms |
183452 KB |
Output is correct |
6 |
Correct |
1313 ms |
183796 KB |
Output is correct |
7 |
Correct |
1065 ms |
182696 KB |
Output is correct |
8 |
Correct |
1296 ms |
184096 KB |
Output is correct |
9 |
Correct |
1306 ms |
176948 KB |
Output is correct |
10 |
Correct |
1248 ms |
176856 KB |
Output is correct |
11 |
Correct |
1262 ms |
180924 KB |
Output is correct |
12 |
Correct |
1285 ms |
180452 KB |
Output is correct |
13 |
Correct |
1382 ms |
183892 KB |
Output is correct |
14 |
Correct |
1336 ms |
180044 KB |
Output is correct |
15 |
Correct |
1329 ms |
183984 KB |
Output is correct |
16 |
Correct |
1355 ms |
179780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
159064 KB |
Output is correct |
2 |
Correct |
54 ms |
159060 KB |
Output is correct |
3 |
Correct |
61 ms |
159056 KB |
Output is correct |
4 |
Correct |
62 ms |
159256 KB |
Output is correct |
5 |
Correct |
68 ms |
159316 KB |
Output is correct |
6 |
Correct |
56 ms |
159324 KB |
Output is correct |
7 |
Correct |
63 ms |
159060 KB |
Output is correct |
8 |
Correct |
58 ms |
159060 KB |
Output is correct |
9 |
Correct |
67 ms |
159064 KB |
Output is correct |
10 |
Correct |
56 ms |
159312 KB |
Output is correct |
11 |
Correct |
74 ms |
159168 KB |
Output is correct |
12 |
Correct |
64 ms |
159060 KB |
Output is correct |
13 |
Correct |
57 ms |
159176 KB |
Output is correct |
14 |
Correct |
1464 ms |
177612 KB |
Output is correct |
15 |
Correct |
1194 ms |
177008 KB |
Output is correct |
16 |
Correct |
152 ms |
172940 KB |
Output is correct |
17 |
Correct |
1294 ms |
176600 KB |
Output is correct |
18 |
Correct |
1325 ms |
176536 KB |
Output is correct |
19 |
Correct |
1295 ms |
176536 KB |
Output is correct |
20 |
Correct |
1185 ms |
176536 KB |
Output is correct |
21 |
Correct |
143 ms |
176620 KB |
Output is correct |
22 |
Correct |
1328 ms |
184296 KB |
Output is correct |
23 |
Correct |
1302 ms |
184148 KB |
Output is correct |
24 |
Correct |
1325 ms |
184396 KB |
Output is correct |
25 |
Correct |
1383 ms |
184396 KB |
Output is correct |
26 |
Correct |
1354 ms |
177724 KB |
Output is correct |
27 |
Correct |
1309 ms |
177916 KB |
Output is correct |
28 |
Correct |
1401 ms |
181104 KB |
Output is correct |
29 |
Correct |
1301 ms |
181072 KB |
Output is correct |
30 |
Correct |
1152 ms |
179620 KB |
Output is correct |
31 |
Correct |
1138 ms |
179676 KB |
Output is correct |
32 |
Correct |
1316 ms |
182536 KB |
Output is correct |
33 |
Correct |
1316 ms |
182652 KB |
Output is correct |
34 |
Correct |
1043 ms |
176976 KB |
Output is correct |
35 |
Correct |
1244 ms |
177652 KB |
Output is correct |
36 |
Correct |
378 ms |
175700 KB |
Output is correct |
37 |
Correct |
1255 ms |
180792 KB |
Output is correct |
38 |
Correct |
1219 ms |
183452 KB |
Output is correct |
39 |
Correct |
1313 ms |
183796 KB |
Output is correct |
40 |
Correct |
1065 ms |
182696 KB |
Output is correct |
41 |
Correct |
1296 ms |
184096 KB |
Output is correct |
42 |
Correct |
1306 ms |
176948 KB |
Output is correct |
43 |
Correct |
1248 ms |
176856 KB |
Output is correct |
44 |
Correct |
1262 ms |
180924 KB |
Output is correct |
45 |
Correct |
1285 ms |
180452 KB |
Output is correct |
46 |
Correct |
1382 ms |
183892 KB |
Output is correct |
47 |
Correct |
1336 ms |
180044 KB |
Output is correct |
48 |
Correct |
1329 ms |
183984 KB |
Output is correct |
49 |
Correct |
1355 ms |
179780 KB |
Output is correct |
50 |
Correct |
1329 ms |
184260 KB |
Output is correct |
51 |
Correct |
1300 ms |
178220 KB |
Output is correct |
52 |
Correct |
1331 ms |
181196 KB |
Output is correct |
53 |
Correct |
1195 ms |
179616 KB |
Output is correct |
54 |
Correct |
1390 ms |
182648 KB |
Output is correct |
55 |
Correct |
1416 ms |
184268 KB |
Output is correct |
56 |
Correct |
1392 ms |
179804 KB |
Output is correct |
57 |
Correct |
1372 ms |
176748 KB |
Output is correct |
58 |
Correct |
1327 ms |
176756 KB |
Output is correct |
59 |
Correct |
1346 ms |
182040 KB |
Output is correct |
60 |
Correct |
1342 ms |
179964 KB |
Output is correct |
61 |
Correct |
1173 ms |
179580 KB |
Output is correct |
62 |
Correct |
1273 ms |
179540 KB |
Output is correct |
63 |
Correct |
1409 ms |
182352 KB |
Output is correct |
64 |
Correct |
1338 ms |
179952 KB |
Output is correct |