#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
vector<int> len[2];
for (int rev = 0; rev < 2; ++rev) {
vector<int> stk = {-1};
for (int i = 0; i < n; ++i) {
while (stk.size() > 1 && v[i] + rev > v[stk.back()])
stk.pop_back();
len[rev].push_back(i - stk.back());
stk.push_back(i);
}
reverse(v.begin(), v.end());
}
reverse(len[1].begin(), len[1].end());
int t = 0;
auto get_range = [&](int i) {
int l = len[0][i] > i ? i : i + max(0LL, t - len[0][i] + 1);
int r = i + min(t + 1, len[1][i]);
return make_pair(l, r);
};
auto cmp = [&](int i, int j) {
assert(i >= 0);
if (j < 0) {
auto [l, r] = get_range(i);
return r < (~j);
}
return i < j;
};
set<int, decltype(cmp)> S(cmp);
for (int i = 0; i < n; ++i)
S.insert(i);
vector<pair<int, long long>> fw(n + 1);
auto update = [&](int i, int k, long long c) {
for (++i; i <= n; i += (i & -i)) {
fw[i].first += k;
fw[i].second += c;
}
};
auto query = [&](int pos) {
int i = *S.lower_bound(~pos);
auto [l, r] = get_range(i);
assert(l <= pos && r >= pos);
long long ans = 1LL * (min(r, pos) - l) * v[i];
for (; i > 0; i -= (i & -i))
ans += 1LL * fw[i].first * t + fw[i].second;
return ans;
};
for (int i = 0; i < n; ++i)
update(i, v[i], v[i]);
vector<tuple<int, int, int>> evs;
for (int i = 0; i < n; ++i) {
evs.emplace_back(len[1][i] - 1, 0, i);
if (len[0][i] <= i) {
evs.emplace_back(len[0][i] - 1, 0, i);
evs.emplace_back(len[0][i] + len[1][i] - 1, 1, i);
}
}
vector<pair<int, int>> qs(q);
for (int i = 0; i < q; ++i) {
int t, l, r; cin >> t >> l >> r;
qs[i] = {l - 1, r};
evs.emplace_back(t, 2, i);
}
sort(evs.begin(), evs.end());
vector<long long> ans(q);
for (auto& [t_, typ, i] : evs) {
t = t_;
if (typ == 0) { // decrease slope
update(i, -v[i], 1LL * t * v[i]);
} else if (typ == 1) { // erase
S.erase(i);
update(i, v[i], -1LL * t * v[i]);
} else { // query
auto [l, r] = qs[i];
ans[i] = query(r) - query(l);
}
}
for (int i = 0; i < q; ++i)
cout << ans[i] << '\n';
return 0;
}
Compilation message
ho_t5.cpp: In lambda function:
ho_t5.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | auto [l, r] = get_range(i);
| ^
ho_t5.cpp: In lambda function:
ho_t5.cpp:54:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [l, r] = get_range(i);
| ^
ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
80 | for (auto& [t_, typ, i] : evs) {
| ^
ho_t5.cpp:88:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | auto [l, r] = qs[i];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
360 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
327 ms |
43836 KB |
Output is correct |
3 |
Correct |
344 ms |
43280 KB |
Output is correct |
4 |
Correct |
357 ms |
43424 KB |
Output is correct |
5 |
Correct |
389 ms |
43772 KB |
Output is correct |
6 |
Correct |
358 ms |
43540 KB |
Output is correct |
7 |
Correct |
336 ms |
43612 KB |
Output is correct |
8 |
Correct |
383 ms |
43812 KB |
Output is correct |
9 |
Correct |
337 ms |
43612 KB |
Output is correct |
10 |
Correct |
359 ms |
43192 KB |
Output is correct |
11 |
Correct |
333 ms |
43756 KB |
Output is correct |
12 |
Correct |
318 ms |
43192 KB |
Output is correct |
13 |
Correct |
381 ms |
43744 KB |
Output is correct |
14 |
Correct |
377 ms |
43700 KB |
Output is correct |
15 |
Correct |
348 ms |
43696 KB |
Output is correct |
16 |
Correct |
355 ms |
43584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
353 ms |
43636 KB |
Output is correct |
3 |
Correct |
345 ms |
42864 KB |
Output is correct |
4 |
Correct |
397 ms |
44112 KB |
Output is correct |
5 |
Correct |
333 ms |
43820 KB |
Output is correct |
6 |
Correct |
349 ms |
43760 KB |
Output is correct |
7 |
Correct |
383 ms |
43908 KB |
Output is correct |
8 |
Correct |
380 ms |
43576 KB |
Output is correct |
9 |
Correct |
397 ms |
43136 KB |
Output is correct |
10 |
Correct |
378 ms |
43384 KB |
Output is correct |
11 |
Correct |
414 ms |
44068 KB |
Output is correct |
12 |
Correct |
392 ms |
44036 KB |
Output is correct |
13 |
Correct |
394 ms |
43904 KB |
Output is correct |
14 |
Correct |
365 ms |
43556 KB |
Output is correct |
15 |
Correct |
346 ms |
44088 KB |
Output is correct |
16 |
Correct |
364 ms |
44000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
480 ms |
43288 KB |
Output is correct |
2 |
Correct |
480 ms |
43476 KB |
Output is correct |
3 |
Correct |
463 ms |
43908 KB |
Output is correct |
4 |
Correct |
496 ms |
43280 KB |
Output is correct |
5 |
Correct |
425 ms |
43388 KB |
Output is correct |
6 |
Correct |
458 ms |
43536 KB |
Output is correct |
7 |
Correct |
521 ms |
43780 KB |
Output is correct |
8 |
Correct |
472 ms |
43632 KB |
Output is correct |
9 |
Correct |
426 ms |
43344 KB |
Output is correct |
10 |
Correct |
484 ms |
43500 KB |
Output is correct |
11 |
Correct |
472 ms |
43272 KB |
Output is correct |
12 |
Correct |
466 ms |
43560 KB |
Output is correct |
13 |
Correct |
447 ms |
43388 KB |
Output is correct |
14 |
Correct |
492 ms |
43608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
360 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
327 ms |
43836 KB |
Output is correct |
34 |
Correct |
344 ms |
43280 KB |
Output is correct |
35 |
Correct |
357 ms |
43424 KB |
Output is correct |
36 |
Correct |
389 ms |
43772 KB |
Output is correct |
37 |
Correct |
358 ms |
43540 KB |
Output is correct |
38 |
Correct |
336 ms |
43612 KB |
Output is correct |
39 |
Correct |
383 ms |
43812 KB |
Output is correct |
40 |
Correct |
337 ms |
43612 KB |
Output is correct |
41 |
Correct |
359 ms |
43192 KB |
Output is correct |
42 |
Correct |
333 ms |
43756 KB |
Output is correct |
43 |
Correct |
318 ms |
43192 KB |
Output is correct |
44 |
Correct |
381 ms |
43744 KB |
Output is correct |
45 |
Correct |
377 ms |
43700 KB |
Output is correct |
46 |
Correct |
348 ms |
43696 KB |
Output is correct |
47 |
Correct |
355 ms |
43584 KB |
Output is correct |
48 |
Correct |
353 ms |
43636 KB |
Output is correct |
49 |
Correct |
345 ms |
42864 KB |
Output is correct |
50 |
Correct |
397 ms |
44112 KB |
Output is correct |
51 |
Correct |
333 ms |
43820 KB |
Output is correct |
52 |
Correct |
349 ms |
43760 KB |
Output is correct |
53 |
Correct |
383 ms |
43908 KB |
Output is correct |
54 |
Correct |
380 ms |
43576 KB |
Output is correct |
55 |
Correct |
397 ms |
43136 KB |
Output is correct |
56 |
Correct |
378 ms |
43384 KB |
Output is correct |
57 |
Correct |
414 ms |
44068 KB |
Output is correct |
58 |
Correct |
392 ms |
44036 KB |
Output is correct |
59 |
Correct |
394 ms |
43904 KB |
Output is correct |
60 |
Correct |
365 ms |
43556 KB |
Output is correct |
61 |
Correct |
346 ms |
44088 KB |
Output is correct |
62 |
Correct |
364 ms |
44000 KB |
Output is correct |
63 |
Correct |
480 ms |
43288 KB |
Output is correct |
64 |
Correct |
480 ms |
43476 KB |
Output is correct |
65 |
Correct |
463 ms |
43908 KB |
Output is correct |
66 |
Correct |
496 ms |
43280 KB |
Output is correct |
67 |
Correct |
425 ms |
43388 KB |
Output is correct |
68 |
Correct |
458 ms |
43536 KB |
Output is correct |
69 |
Correct |
521 ms |
43780 KB |
Output is correct |
70 |
Correct |
472 ms |
43632 KB |
Output is correct |
71 |
Correct |
426 ms |
43344 KB |
Output is correct |
72 |
Correct |
484 ms |
43500 KB |
Output is correct |
73 |
Correct |
472 ms |
43272 KB |
Output is correct |
74 |
Correct |
466 ms |
43560 KB |
Output is correct |
75 |
Correct |
447 ms |
43388 KB |
Output is correct |
76 |
Correct |
492 ms |
43608 KB |
Output is correct |
77 |
Correct |
352 ms |
48256 KB |
Output is correct |
78 |
Correct |
354 ms |
49196 KB |
Output is correct |
79 |
Correct |
375 ms |
48912 KB |
Output is correct |
80 |
Correct |
385 ms |
48364 KB |
Output is correct |
81 |
Correct |
395 ms |
48052 KB |
Output is correct |
82 |
Correct |
339 ms |
48620 KB |
Output is correct |
83 |
Correct |
375 ms |
48384 KB |
Output is correct |
84 |
Correct |
364 ms |
48168 KB |
Output is correct |
85 |
Correct |
393 ms |
48876 KB |
Output is correct |
86 |
Correct |
364 ms |
48396 KB |
Output is correct |
87 |
Correct |
379 ms |
49428 KB |
Output is correct |
88 |
Correct |
386 ms |
49148 KB |
Output is correct |
89 |
Correct |
351 ms |
47900 KB |
Output is correct |
90 |
Correct |
332 ms |
48884 KB |
Output is correct |
91 |
Correct |
377 ms |
48116 KB |
Output is correct |
92 |
Correct |
325 ms |
47688 KB |
Output is correct |
93 |
Correct |
383 ms |
48400 KB |
Output is correct |
94 |
Correct |
339 ms |
49688 KB |
Output is correct |
95 |
Correct |
366 ms |
49280 KB |
Output is correct |
96 |
Correct |
374 ms |
48528 KB |
Output is correct |
97 |
Correct |
333 ms |
48612 KB |
Output is correct |
98 |
Correct |
369 ms |
47760 KB |
Output is correct |
99 |
Correct |
364 ms |
48164 KB |
Output is correct |
100 |
Correct |
397 ms |
48480 KB |
Output is correct |
101 |
Correct |
366 ms |
47956 KB |
Output is correct |
102 |
Correct |
388 ms |
48956 KB |
Output is correct |