#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()
/*
Date: 2022/08/24 15:14
Problem Link: https://oj.uz/problem/view/JOI19_jumps
Topic(s):
Time Spent:
Solution Notes:
Consider pairs of possible (a, b), and let them be at indices (i, j). We observe that in range [i, j], a and b must
be the two largest element, and everything in between is smaller.
Therefore, we can fix whichever one of a or b that's smaller, and then find the other endpoint in O(N) time in total
by using a monotone stack.
One we have all (a, b), it is a matter of determining c. We can naively use a segment tree to query every c (subtask 2),
or use a suffix max (subtask 3).
To get the full solution, let's store the value of a + b at the least location of c that it corresponds to. Each node in
segment tree would essientially store the following values:
1. max a+b
2. max c
3. max a+b+c
*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
const int MAXN = 2e5+5, INF = 1e9;
int n, q;
struct Node{
int ab, c, abc;
};
struct segtree{
const int PO2 = 131072; // least power of 2 greater than MAXN;
int n;
Node identity = {-INF, -INF, -INF};
vector<Node> seg;
vector<int> arr;
void init(int n){
this->n = n;
seg.resize(4*n, identity); // change to 4*N if we want to reinitialize the segtree multiple times on difference values of N
}
ll query(int a, int b){
if (a > b){
return -INF;
}
return query(0, 0, n-1, a, b).abc;
}
Node query(int node, int l, int r, int a, int b) { // inclusive 0-indexed
if (a <= l && r <= b) {
return seg[node];
}
Node ans = identity;
int mid = (l + r) / 2;
if (a <= mid) {
ans = combine(ans, query(node * 2 + 1, l, mid, a, b));
}
if (b > mid){
ans = combine(ans, query(node * 2 + 2, mid + 1, r, a, b));
}
return ans;
}
void update(int a, int x, bool updC) { // inclusive 0-indexed
if (a >= n){
return;
}
update(0, 0, n-1, a, x, updC);
}
void update(int node, int l, int r, int a, int x, bool updC) {
if (l == r) {
if (updC){
seg[node].c = x;
}else{
seg[node].ab = x;
}
seg[node].abc = seg[node].ab + seg[node].c;
return;
}
int mid = (l + r) / 2;
if (a <= mid) {
update(node * 2 + 1, l, mid, a, x, updC);
}else{
update(node * 2 + 2, mid + 1, r, a, x, updC);
}
seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
}
Node combine(Node a, Node b){
return {max(a.ab, b.ab), max(a.c, b.c), max({a.abc, b.abc, a.ab + b.c})};
}
};
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n;
vector<int> arr(n);
for (int i=0; i<n; i++){
cin >> arr[i];
}
// use monotonic stack to process the possible (a, b).
// assume a > b
vector<pii> ab;
stack<pii> st;
for (int i=n-1; i>=0; i--){
while (!st.empty() && st.top().first < arr[i]){
st.pop();
}
if (!st.empty()){
ab.push_back({i, st.top().second});
}
st.push({arr[i], i});
}
stack<pii> st2;
swap(st2, st);
for (int i=0; i<n; i++){
while (!st.empty() && st.top().first < arr[i]){
st.pop();
}
if (!st.empty()){
ab.push_back({st.top().second, i});
}
st.push({arr[i], i});
}
dbg(ab)
segtree seg;
seg.init(n);
sort(ab.begin(), ab.end(), greater<pii>());
int pt = 0;
vector<array<int, 3>> queries;
cin >> q;
for (int i=0; i<q; i++){
int l, r;
cin >> l >> r;
l--; r--;
queries.push_back({l, r, i});
}
sort(queries.begin(), queries.end(), [](const array<int, 3> a1, const array<int, 3> a2){
return make_pair(a1[0], a1[1]) > make_pair(a2[0], a2[1]);
});
for (int i=0; i<n; i++){
seg.update(i, arr[i], true);
}
vector<int> ans(q);
for (int i=0; i<q; i++){
while (pt < sz(ab) && ab[pt].first >= queries[i][0]){
seg.update(ab[pt].second + (ab[pt].second - ab[pt].first), arr[ab[pt].first] + arr[ab[pt].second], false);
pt++;
}
ans[queries[i][2]] = seg.query(queries[i][0], queries[i][1]);
}
for (int i : ans){
cout << i << "\n";
}
}
/**
* Debugging checklist:
* - Reset everything after each TC
* - Integer overflow, index overflow
* - Special cases?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
15400 KB |
Output is correct |
| 2 |
Correct |
112 ms |
15420 KB |
Output is correct |
| 3 |
Correct |
105 ms |
15448 KB |
Output is correct |
| 4 |
Correct |
170 ms |
15504 KB |
Output is correct |
| 5 |
Correct |
176 ms |
15500 KB |
Output is correct |
| 6 |
Correct |
192 ms |
14852 KB |
Output is correct |
| 7 |
Correct |
164 ms |
14672 KB |
Output is correct |
| 8 |
Correct |
166 ms |
14740 KB |
Output is correct |
| 9 |
Correct |
163 ms |
15068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
