#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define forde(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, q;
ll d[N], tr[N << 2], lazy[N << 2], ans[N], sp[17][N];
struct query {
int f, l, pos;
};
query r[N];
void build() {
forin(i,1,n) sp[0][i] = d[i];
forin(j,1,log2(n)) {
forin(i,1,n - (1 << j - 1) + 1) {
sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
}
}
}
ll mx(int f, int l) {
if(f == l) return d[f];
int j = log2(l - f + 1);
return max(sp[j][f], sp[j][l - (1 << j) + 1]);
}
void push(int id, int f, int l) {
ll t = lazy[id];
if(t) {
tr[id] = max(tr[id], t + mx(f, l));
if(f < l) {
lazy[id << 1] = max(lazy[id << 1], t);
lazy[id << 1 | 1] = max(lazy[id << 1 | 1], t);
}
lazy[id] = 0;
}
}
void up(int u, int v, ll val, int id = 1, int f = 1, int l = n) {
push(id, f, l);
if(v < f || l < u) return;
if(u <= f && l <= v) {
lazy[id] = max(lazy[id], val);
push(id, f, l);
return;
}
int mid = f + l >> 1;
up(u, v, val, id << 1, f, mid);
up(u, v, val, id << 1 | 1, mid + 1, l);
tr[id] = max(tr[id << 1], tr[id << 1 | 1]);
}
ll get(int u, int v, int id = 1, int f = 1, int l = n) {
push(id, f, l);
if(v < f || l < u) return 0;
if(u <= f && l <= v) return tr[id];
int mid = f + l >> 1;
return max(get(u, v, id << 1, f, mid), get(u, v, id << 1 | 1, mid + 1, l));
}
int main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("Task.inp","r")) {
freopen("Task.inp","r",stdin);
freopen("WA.out","w",stdout);
}
cin>>n;
forin(i,1,n) cin>>d[i];
build();
cin>>q;
forin(i,1,q) {
r[i].pos = i;
cin>>r[i].f>>r[i].l;
}
sort(r + 1, r + q + 1, [] (query a, query b) {
return a.f > b.f;
});
stack<int> st;
vector<pair<int, int>> vt;
vt.push_back({0, 0});
forde(i,n,1) {
while(!st.empty() && d[st.top()] <= d[i]) {
vt.push_back({i, st.top()});
st.pop();
}
if(!st.empty()) vt.push_back({i, st.top()});
st.push(i);
}
int j = 1;
forin(i,1,q) {
while(j <= vt.size() - 1 && vt[j].first >= r[i].f) {
int a, b; tie(a, b) = vt[j++];
if(2 * b - a > n) continue;
up(2 * b - a, n, d[a] + d[b]);
}
ans[r[i].pos] = get(r[i].f, r[i].l);
}
forin(i,1,q) cout<<ans[i]<<"\n";
}
Compilation message
jumps.cpp: In function 'void build()':
jumps.cpp:16:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
16 | forin(i,1,n - (1 << j - 1) + 1) {
| ~~^~~
jumps.cpp:2:37: note: in definition of macro 'forin'
2 | #define forin(i,a,b) for(int i=a;i<=b;++i)
| ^
jumps.cpp:17:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
17 | sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
| ~~^~~
jumps.cpp: In function 'void up(int, int, long long int, int, int, int)':
jumps.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int mid = f + l >> 1;
| ~~^~~
jumps.cpp: In function 'long long int get(int, int, int, int, int)':
jumps.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = f + l >> 1;
| ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while(j <= vt.size() - 1 && vt[j].first >= r[i].f) {
| ~~^~~~~~~~~~~~~~~~
jumps.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
430 ms |
19616 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
45592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
430 ms |
19616 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
