#include <bits/stdc++.h>
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
template <class T>
using Vec = std::vector<T>;
constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;
struct Mn {
u32 whole, value;
static Mn id() {
return Mn { 0, 0 };
}
Mn operator + (const Mn other) const {
return Mn { std::max(whole, other.whole), std::max(value, other.value) };
}
};
struct Ef {
u32 add;
static Ef id() {
return Ef { 0 };
}
Ef operator + (const Ef other) const {
return Ef { std::max(add, other.add) };
}
};
Mn operator + (const Mn mn, const Ef ef) {
return Mn { std::max(mn.whole, mn.value + ef.add), mn.value };
}
struct Segtree {
struct Node {
Mn mn;
Ef ef;
};
void fetch(const usize i) {
data[i].mn = data[i * 2 + 0].mn + data[i * 2 + 1].mn;
}
void apply(const usize i, const Ef ef) {
data[i].mn = data[i].mn + ef;
data[i].ef = data[i].ef + ef;
}
void flush(const usize i) {
apply(i * 2 + 0, data[i].ef);
apply(i * 2 + 1, data[i].ef);
}
static usize ctzr(const usize i) {
return __builtin_ctzll(i);
}
static usize height(const usize i) {
return 64 - __builtin_clzll(i);
}
void pushdown(const usize i) {
const auto lsb = ctzr(i);
for (usize d = height(i); --d > lsb;) {
flush(i >> d);
}
}
void pullup(usize i) {
i >>= ctzr(i);
while (i != 1) {
i >>= 1;
fetch(i);
}
}
std::vector<Node> data;
Segtree(const std::vector<u32> &vec) {
const auto size = vec.size();
data.resize(size * 2, Node { Mn::id(), Ef::id() });
for (usize i = 0; i < size; ++i) {
data[size + i].mn.whole = vec[i];
data[size + i].mn.value = vec[i];
}
for (usize i = size - 1; i > 0; --i) {
fetch(i);
}
}
void operate(usize l, usize r, const u32 x) {
l += size();
r += size();
pushdown(l);
pushdown(r);
const auto cl = l;
const auto cr = r;
const auto ef = Ef { x };
while (l < r) {
if (l & 1) {
apply(l, ef);
l += 1;
}
if (r & 1) {
r -= 1;
apply(r, ef);
}
l >>= 1;
r >>= 1;
}
pullup(cl);
pullup(cr);
}
u32 fold(usize l, usize r) {
l += size();
r += size();
pushdown(l);
pushdown(r);
Mn mn = Mn::id();
while (l < r) {
if (l & 1) {
mn = mn + data[l].mn;
l += 1;
}
if (r & 1) {
r -= 1;
mn = mn + data[r].mn;
}
l >>= 1;
r >>= 1;
}
return mn.whole;
}
usize size() const {
return data.size() / 2;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
usize N;
std::cin >> N;
Vec<u32> A(N);
for (auto &x: A) {
std::cin >> x;
}
std::vector<std::vector<usize>> cand(N);
std::stack<usize> stack;
for (usize m = 0; m < N - 1; ++m) {
while (!stack.empty()) {
const auto l = stack.top();
if (m + (m - l) < N) {
cand[l].push_back(m);
}
if (A[l] > A[m]) {
break;
}
stack.pop();
}
stack.push(m);
}
usize Q;
std::cin >> Q;
std::vector<std::vector<std::pair<usize, usize>>> query(N);
for (usize i = 0; i < Q; ++i) {
usize l, r;
std::cin >> l >> r;
l -= 1;
query[l].emplace_back(i, r);
}
Segtree seg(A);
std::vector<usize> ans(Q);
for (usize l = N; l --> 0;) {
for (const auto m: cand[l]) {
const auto r = m + (m - l);
seg.operate(r, N, A[l] + A[m]);
}
for (const auto [i, r]: query[l]) {
ans[i] = seg.fold(l + 2, r);
}
}
for (const auto x: ans) {
std::cout << x << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
392 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
392 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
322 ms |
27968 KB |
Output is correct |
12 |
Correct |
316 ms |
27928 KB |
Output is correct |
13 |
Correct |
292 ms |
27884 KB |
Output is correct |
14 |
Correct |
311 ms |
28012 KB |
Output is correct |
15 |
Correct |
308 ms |
27964 KB |
Output is correct |
16 |
Correct |
314 ms |
27372 KB |
Output is correct |
17 |
Correct |
298 ms |
27360 KB |
Output is correct |
18 |
Correct |
305 ms |
27216 KB |
Output is correct |
19 |
Correct |
293 ms |
27884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
24428 KB |
Output is correct |
2 |
Correct |
98 ms |
23148 KB |
Output is correct |
3 |
Correct |
101 ms |
24812 KB |
Output is correct |
4 |
Correct |
167 ms |
24556 KB |
Output is correct |
5 |
Correct |
187 ms |
24428 KB |
Output is correct |
6 |
Correct |
165 ms |
23916 KB |
Output is correct |
7 |
Correct |
164 ms |
23788 KB |
Output is correct |
8 |
Correct |
168 ms |
23916 KB |
Output is correct |
9 |
Correct |
167 ms |
24164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
392 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
322 ms |
27968 KB |
Output is correct |
12 |
Correct |
316 ms |
27928 KB |
Output is correct |
13 |
Correct |
292 ms |
27884 KB |
Output is correct |
14 |
Correct |
311 ms |
28012 KB |
Output is correct |
15 |
Correct |
308 ms |
27964 KB |
Output is correct |
16 |
Correct |
314 ms |
27372 KB |
Output is correct |
17 |
Correct |
298 ms |
27360 KB |
Output is correct |
18 |
Correct |
305 ms |
27216 KB |
Output is correct |
19 |
Correct |
293 ms |
27884 KB |
Output is correct |
20 |
Correct |
168 ms |
24428 KB |
Output is correct |
21 |
Correct |
98 ms |
23148 KB |
Output is correct |
22 |
Correct |
101 ms |
24812 KB |
Output is correct |
23 |
Correct |
167 ms |
24556 KB |
Output is correct |
24 |
Correct |
187 ms |
24428 KB |
Output is correct |
25 |
Correct |
165 ms |
23916 KB |
Output is correct |
26 |
Correct |
164 ms |
23788 KB |
Output is correct |
27 |
Correct |
168 ms |
23916 KB |
Output is correct |
28 |
Correct |
167 ms |
24164 KB |
Output is correct |
29 |
Correct |
1020 ms |
88912 KB |
Output is correct |
30 |
Correct |
812 ms |
86308 KB |
Output is correct |
31 |
Correct |
812 ms |
90296 KB |
Output is correct |
32 |
Correct |
998 ms |
89324 KB |
Output is correct |
33 |
Correct |
994 ms |
89280 KB |
Output is correct |
34 |
Correct |
991 ms |
87164 KB |
Output is correct |
35 |
Correct |
1012 ms |
86652 KB |
Output is correct |
36 |
Correct |
1000 ms |
86632 KB |
Output is correct |
37 |
Correct |
1006 ms |
88300 KB |
Output is correct |
38 |
Correct |
740 ms |
91884 KB |
Output is correct |
39 |
Correct |
731 ms |
92012 KB |
Output is correct |
40 |
Correct |
718 ms |
88588 KB |
Output is correct |
41 |
Correct |
719 ms |
88112 KB |
Output is correct |
42 |
Correct |
727 ms |
88208 KB |
Output is correct |
43 |
Correct |
725 ms |
89804 KB |
Output is correct |
44 |
Correct |
762 ms |
92176 KB |
Output is correct |
45 |
Correct |
755 ms |
92268 KB |
Output is correct |
46 |
Correct |
753 ms |
89108 KB |
Output is correct |
47 |
Correct |
740 ms |
88812 KB |
Output is correct |
48 |
Correct |
743 ms |
88556 KB |
Output is correct |
49 |
Correct |
748 ms |
90732 KB |
Output is correct |
50 |
Correct |
835 ms |
92364 KB |
Output is correct |
51 |
Correct |
824 ms |
92404 KB |
Output is correct |
52 |
Correct |
812 ms |
89964 KB |
Output is correct |
53 |
Correct |
810 ms |
89708 KB |
Output is correct |
54 |
Correct |
815 ms |
89704 KB |
Output is correct |
55 |
Correct |
813 ms |
91208 KB |
Output is correct |