//
// Created by Ильдар Ялалов on 14.01.2020.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 8e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
typedef unsigned int uint;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()
#ifdef zxc
#include "debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#define debug_arr(...) 42
#endif
bool debug = 0;
const int MAXN = (1e6) + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (3e6 + 10);
int arr[MAXN];
int res[MAXN];
vector<int> add[MAXN];
#define left v<<1,tl,tm
#define right v<<1|1,tm+1,tr
int c[4 * MAXN];
int ab[4 * MAXN];
int val[4 * MAXN];
void calc(int v) {
c[v] = max(c[v << 1], c[v << 1 | 1]);
val[v] = max(val[v], max(val[v << 1], val[v << 1 | 1]));
}
void build(int v, int tl, int tr) {
if (tl == tr) {
c[v] = arr[tl];
val[v] = 0;
ab[v] = 0;
} else {
int tm = (tl + tr) >> 1;
ab[v] = val[v] = 0;
build(left);
build(right);
calc(v);
}
}
void push(int v) {
int v1 = (v << 1);
int v2 = (v << 1 | 1);
ab[v1] = max(ab[v1], ab[v]);
ab[v2] = max(ab[v2], ab[v]);
val[v1] = max(val[v1], ab[v1] + c[v1]);
val[v2] = max(val[v2], ab[v2] + c[v2]);
}
void update(int v, int tl, int tr, int l, int r, int x) {
if (l > tr || r < tl)
return;
if (l <= tl && tr <= r) {
ab[v] = max(ab[v], x);
val[v] = max(val[v], c[v] + ab[v]);
} else {
int tm = (tl + tr) >> 1;
push(v);
update(left, l, r, x);
update(right, l, r, x);
calc(v);
}
}
int get(int v, int tl, int tr, int l, int r) {
if (l > tr || r < tl)
return -inf_int;
if (l <= tl && tr <= r) {
return val[v];
} else {
int tm = (tl + tr) >> 1;
push(v);
int res1 = get(left, l, r);
int res2 = get(right, l, r);
calc(v);
return max(res1, res2);
}
}
void solve() {
int n, q;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
cin >> q;
vector<pair<pii, int> > cc;
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
cc.pb({{l, r}, i});
}
sort(all(cc));
vector<pii> pairs;
stack<int> st;
for (int i = 1; i <= n; ++i) {
while (!st.empty() && arr[i] >= arr[st.top()]) {
pairs.pb({st.top(), i});
st.pop();
}
if (!st.empty()) {
pairs.pb({st.top(), i});
st.pop();
}
st.push(i);
}
debug(pairs);
for (auto x : pairs) {
add[x.fi].pb(x.se);
}
debug(cc);
int top = sz(cc) - 1;
build(1, 0, n);
for (int a = n; a >= 1; --a) {
debug(a);
for (int b : add[a]) {
int st = 2 * b - a;
debug(a, b, st);
update(1, 0, n, st, n, arr[a] + arr[b]);
}
while (top >= 0 && cc[top].fi.fi >= a) {
int r = cc[top].fi.se;
int id = cc[top].se;
debug("ask", a, r);
res[id] = get(1, 0, n, a, r);
top--;
}
}
for (int i = 1; i <= q; ++i) {
cout << res[i] << "\n";
}
}
// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES ( n==1)
signed main() {
#ifdef zxc
freopen("../output.txt", "r", stdin);
// freopen("../output1.txt", "w", stdout);
#else
#endif //zxc
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout.setf(ios::fixed);
cout.precision(15);
int t = 1;
while (t--)
solve();
debug(1.0 * clock() / CLOCKS_PER_SEC);
}
Compilation message
jumps.cpp: In function 'void solve()':
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:145:5: note: in expansion of macro 'debug'
145 | debug(pairs);
| ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:153:5: note: in expansion of macro 'debug'
153 | debug(cc);
| ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:159:9: note: in expansion of macro 'debug'
159 | debug(a);
| ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:162:13: note: in expansion of macro 'debug'
162 | debug(a, b, st);
| ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:169:13: note: in expansion of macro 'debug'
169 | debug("ask", a, r);
| ^~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
36 | #define debug(...) 42
| ^~
jumps.cpp:202:5: note: in expansion of macro 'debug'
202 | debug(1.0 * clock() / CLOCKS_PER_SEC);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
38636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
