| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 348321 | Vanjanja | Triple Jump (JOI19_jumps) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 500001;
int a[N];
pair<pair<int, int>, int> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[2 * N - 1][2];
int lazy[2 * N - 1];
int n;
int index = 0;
void build(int u, int l, int r) {
if (l == r) {
seg[u][1] = a[l];
return;
}
int mid = l + r >> 1;
build(u * 2 + 1, l, mid);
build(u * 2 + 2, mid + 1, r);
seg[u][1] = max(seg[u * 2 + 1][1], seg[u * 2 + 2][1]);
}
void upd(int u, int x) {
seg[u][0] = max(seg[u][0], x + seg[u][1]);
lazy[u] = max(lazy[u], x);
}
void shift(int u) {
lazy[u * 2 + 1] = lazy[u];
lazy[u * 2 + 2] = lazy[u];
seg[u * 2 + 1][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 1][1] + lazy[u]);
seg[u * 2 + 2][0] = max(seg[u * 2 + 2][0], seg[u * 2 + 2][1] + lazy[u]);
lazy[u] = 0;
}
void update(int u, int l, int r, int L, int R, int x) {
if (r < L || l > R)
return;
if (l >= L && r <= R) {
upd(u, x);
return;
}
if (lazy[u])
shift(u);
int mid = l + r >> 1;
update(u * 2 + 1, l, mid, L, R, x);
update(u * 2 + 2, mid + 1, r, L, R, x);
seg[u][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 2][0]);
}
void Update(int x, int y) {
for (int i = y - 1; i >= x; i--) {
if (b[i] != -1) {
int l = 2 * b[i] - i;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[i] + a[b[i]]);
}
}
while (c[index].first == i) {
int l = 2 * c[index].second - c[index].first;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[c[index].first] + a[c[index].second]);
}
index++;
}
}
}
int out(int u, int l, int r, int L, int R) {
if (r < L || l > R)
return 0;
if (l >= L && r <= R) {
return seg[u][0];
}
if (lazy[u])
shift(u);
int mid = l + r >> 1;
return max(out(u * 2 + 1, l, mid, L, R), out(u * 2 + 2, mid + 1, r, L, R));
}
void veca(int n) {
stack<pair<int, int>> s;
s.push(make_pair(a[0], 0));
for (int i = 1; i < n; i++) {
pair<int, int> top = s.top();
while (!s.empty() && top.first <= a[i]) {
b[top.second] = i;
s.pop();
if (!s.empty())
top = s.top();
}
s.push(make_pair(a[i], i));
}
while (!s.empty()) {
pair<int, int> top = s.top();
b[top.second] = -1;
s.pop();
}
}
bool cmp1(pair<int, int> x, pair<int, int> y) {
if (x.first > y.first)
return true;
if (x.second < y.second)
return true;
return false;
}
void veca1(int n) {
stack<pair<int, int>> s;
s.push(make_pair(a[n - 1], n - 1));
for (int i = n - 2; i >= 0; i--) {
pair<int, int> top = s.top();
while (!s.empty() && top.first <= a[i]) {
c[top.second].first = i;
c[top.second].second = top.second;
s.pop();
if (!s.empty())
top = s.top();
}
s.push(make_pair(a[i], i));
}
while (!s.empty()) {
pair<int, int> top = s.top();
c[top.second].first = -1;
s.pop();
}
sort(c, c + n, cmp1);
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.first.first >= b.first.first;
}
void solve() {
int q;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> q;
for (int i = 0; i < q; i++) {
cin >> que[i].first.first >> que[i].first.second;
que[i].second = i;
}
veca(n);
veca1(n);
sort(que, que + q, cmp);
build(0, 0, n - 1);
for (int i = 0; i < q; i++) {
if (i == 0)
Update(que[i].first.first - 1, n);
else
Update(que[i].first.first - 1, que[i - 1].first.first - 1);
resenje[que[i].second] = out(0, 0, n - 1, que[i].first.first - 1, que[i].first.second - 1);
}
for (int i = 0; i < q; i++)
cout << resenje[i] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}