/*
Code for problem D by cookiedoth
Generated 16 Feb 2020 at 02.47 P
──────▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▌
───▄▄██▌█░ВЕЗЁМ▄▀▀▀▄░ГУСЕЙ░░░░░░░
───████▌█▄███▀░◐░▄▀▀▀▄░░РАБОТЯГИ░
──██░░█▌█░░▄███▀░◐░░▄▀▀▀▄░░░░░░░
─██░░░█▌█░░░░▐░▄▀▀▀▌░░░░◐░▀███▄░
▄██████▌█▄███▀░◐░░░▌░░░░░▐░░░░░░
███████▌█░░░░▌░░░░░▌░░░░░▐░░░░░░
███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▌
▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀▀▀(@)▀(@)
-_-
z_z
=_=
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()
using namespace std;
template<class T> int chkmax(T &a, T b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
template<class T> int chkmin(T &a, T b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
while (begin != end) {
out << (*begin) << " ";
begin++;
}
out << endl;
}
template<class T> void output(T x, ostream& out = cerr) {
output(x.begin(), x.end(), out);
}
void fast_io() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
/** Fast input-output */
template <class T = int> inline T readInt();
inline double readDouble();
inline int readUInt();
inline int readChar(); // first non-blank character
inline void readWord(char *s);
inline bool readLine(char *s); // do not save '\n'
inline bool isEof();
inline int getChar();
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
template <class T> inline void writeInt(T x, char end = 0, int len = -1);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void writeDouble(double x, int len = 0);
inline void flush();
static struct buffer_flusher_t {
~buffer_flusher_t() {
flush();
}
} buffer_flusher;
/** Read */
static const int buf_size = 4096;
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline bool isEof() {
if (buf_pos == buf_len) {
buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
if (buf_pos == buf_len)
return 1;
}
return 0;
}
inline int getChar() {
return isEof() ? -1 : buf[buf_pos++];
}
inline int peekChar() {
return isEof() ? -1 : buf[buf_pos];
}
inline bool seekEof() {
int c;
while ((c = peekChar()) != -1 && c <= 32)
buf_pos++;
return c == -1;
}
inline void skipBlanks() {
while (!isEof() && buf[buf_pos] <= 32U)
buf_pos++;
}
inline int readChar() {
int c = getChar();
while (c != -1 && c <= 32)
c = getChar();
return c;
}
inline int readUInt() {
int c = readChar(), x = 0;
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return x;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
else if (c == '+')
c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
inline double readDouble() {
int s = 1, c = readChar();
double x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
if (c == '.') {
c = getChar();
double coef = 1;
while ('0' <= c && c <= '9')
x += (c - '0') * (coef *= 1e-1), c = getChar();
}
return s == 1 ? x : -x;
}
inline void readWord(char *s) {
int c = readChar();
while (c > 32)
*s++ = c, c = getChar();
*s = 0;
}
inline bool readLine(char *s) {
int c = getChar();
while (c != '\n' && c != -1)
*s++ = c, c = getChar();
*s = 0;
return c != -1;
}
/** Write */
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
if (write_buf_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
write_buf[write_buf_pos++] = x;
}
inline void flush() {
if (write_buf_pos) {
fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
fflush(stdout);
}
}
template <class T>
inline void writeInt(T x, char end, int output_len) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n < output_len)
s[n++] = '0';
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord(const char *s) {
while (*s)
writeChar(*s++);
}
inline void writeDouble(double x, int output_len) {
if (x < 0)
writeChar('-'), x = -x;
int t = (int)x;
writeInt(t), x -= t;
writeChar('.');
for (int i = output_len - 1; i > 0; i--) {
x *= 10;
t = std::min(9, (int)x);
writeChar('0' + t), x -= t;
}
x *= 10;
t = std::min(9, (int)(x + 0.5));
writeChar('0' + t);
}
const int INF = 1e9;
struct rmq {
vector<int> t;
int n;
rmq() {}
void build(int *a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) >> 1;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
void build(int *a, int _n) {
n = 1;
while (n < _n) {
n <<= 1;
}
t.resize(2 * n);
build(a, 1, 0, n - 1);
}
void init(int _n) {
n = 1;
while (n < _n) {
n <<= 1;
}
t.resize(2 * n);
}
int get(int l, int r) {
l += n;
r += n;
int res = 0;
while (l <= r) {
if (l & 1) {
chkmax(res, t[l]);
l++;
}
if ((r & 1) == 0) {
chkmax(res, t[r]);
r--;
}
l >>= 1;
r >>= 1;
}
return res;
}
void update(int pos, int val) {
int v = pos + n;
t[v] = val;
while (v > 1) {
v >>= 1;
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
};
ll C = 0;
struct stb {
vector<int> min_val1, min_val2, max_res1, max_res2, mod;
int n;
stb() {}
void init(int _n) {
n = _n;
// cerr << "init " << _n << endl;
min_val1.resize(4 * n, -INF);
min_val2.resize(4 * n, -INF);
max_res1.resize(4 * n, -2 * INF);
max_res2.resize(4 * n, -2 * INF);
mod.resize(4 * n, 0);
}
void push(int v) {
if (min_val1[v * 2] + mod[v * 2] == min_val1[v]) {
mod[v * 2] += mod[v];
}
if (min_val1[v * 2 + 1] + mod[v * 2 + 1] == min_val1[v]) {
mod[v * 2 + 1] += mod[v];
}
max_res1[v] += mod[v];
if (min_val1[v] == min_val2[v]) {
min_val2[v] += mod[v];
}
min_val1[v] += mod[v];
mod[v] = 0;
}
void merge(int v, int v1) {
// cerr << "merge " << v << " " << v1 << " " << min_val1[v1] << " " << min_val2[v1] << " " << max_res1[v1] << " " << max_res2[v1] << endl;
if (min_val1[v1] + mod[v1] == min_val1[v]) {
chkmax(max_res1[v], max_res1[v1] + mod[v1]);
} else {
chkmin(min_val2[v], min_val1[v1] + mod[v1]);
chkmax(max_res2[v], max_res1[v1] + mod[v1]);
}
if (min_val2[v1] != min_val1[v1]) {
chkmin(min_val2[v], min_val2[v1]);
chkmax(max_res2[v], max_res2[v1]);
}
}
void recalc(int v) {
// cerr << "uhuhuhu " << v << " " << max_res1[v * 2] << " " << max_res2[v * 2] << " " << max_res1[v * 2 + 1] << " " << max_res2[v * 2 + 1] << endl;
// cerr << "mododod " << mod[v * 2] << " " << mod[v * 2 + 1] << endl;
min_val1[v] = min(min_val1[v * 2] + mod[v * 2], min_val1[v * 2 + 1] + mod[v * 2 + 1]);
min_val2[v] = INF;
max_res1[v] = -2 * INF;
max_res2[v] = -2 * INF;
merge(v, 2 * v);
merge(v, v * 2 + 1);
if (min_val2[v] == INF) {
min_val2[v] = min_val1[v];
}
// cerr << "recalced " << v << endl;
// cerr << min_val1[v] << " " << min_val2[v] << " " << max_res1[v] << " " << max_res2[v] << endl;
}
void update(int val, int v, int tl, int tr) {
C++;
if (min_val1[v] == min_val2[v] || val < min_val2[v]) {
if (val > min_val1[v] + mod[v]) {
mod[v] = val - min_val1[v];
}
// cerr << "mod " << v << " = " << mod[v] << endl;
return;
} else {
int tm = (tl + tr) >> 1;
push(v);
update(val, v * 2, tl, tm);
update(val, v * 2 + 1, tm + 1, tr);
recalc(v);
}
}
void chkmax_val(int val) {
// cerr << "QUERY: chkmax_val " << val << endl;
update(val, 1, 0, n - 1);
}
void update_val(int pos, int val, int v, int tl, int tr) {
if (tl == tr) {
int delta = (val - min_val1[v] - mod[v]);
min_val1[v] = min_val2[v] = val;
max_res1[v] += (mod[v] + delta);
max_res2[v] = -2 * INF;
mod[v] = 0;
} else {
int tm = (tl + tr) >> 1;
push(v);
if (pos <= tm) {
update_val(pos, val, v * 2, tl, tm);
} else {
update_val(pos, val, v * 2 + 1, tm + 1, tr);
}
recalc(v);
}
}
void change_val(int pos, int val) {
// cerr << "QUERY: change_val " << pos << " " << val << endl;
update_val(pos, val, 1, 0, n - 1);
}
void update_sum(int pos, int val, int v, int tl, int tr) {
if (tl == tr) {
max_res1[v] = val + min_val1[v];
// cerr << "max_res1 " << v << " = " << max_res1[v] << endl;
} else {
int tm = (tl + tr) >> 1;
push(v);
if (pos <= tm) {
update_sum(pos, val, v * 2, tl, tm);
} else {
update_sum(pos, val, v * 2 + 1, tm + 1, tr);
}
recalc(v);
}
}
void change_sum(int pos, int val) {
// cerr << "QUERY: change_sum " << pos << " " << val << endl;
update_sum(pos, val, 1, 0, n - 1);
}
int get(int l, int r, int v, int tl, int tr) {
if (r < tl || l > tr) {
return -2 * INF;
}
if (l <= tl && tr <= r) {
return max(max_res1[v] + mod[v], max_res2[v]);
}
int tm = (tl + tr) >> 1;
push(v);
int res_l = get(l, r, v * 2, tl, tm);
int res_r = get(l, r, v * 2 + 1, tm + 1, tr);
return max(res_l, res_r);
}
int get(int l, int r) {
int res = get(l, r, 1, 0, n - 1);
// cerr << "QUERY: get " << l << " " << r << " = " << res << endl;
return res;
}
};
const int mx = 5e5 + 1e4;
int n, arr[mx], m, ans[mx];
vector<vector<pair<int, int> > > lq, rseg, sum_update, val_update;
rmq arr_rmq, q_rmq;
stb T;
void read() {
n = readInt();
if (n > 500000) {
exit(0);
}
for (int i = 0; i < n; ++i) {
arr[i] = readInt();
}
lq.resize(n);
m = readInt();
if (m > 500000) {
exit(0);
}
for (int i = 0; i < m; ++i) {
int l, r;
l = readInt();
r = readInt();
l--;
r--;
lq[r].emplace_back(l, i);
}
}
void add(int a, int b) {
// cerr << "add " << a << " " << b << endl;
int c = b + (b - a);
int sum = arr[a] + arr[b];
if (c < n) {
rseg[a].emplace_back(c, sum);
}
}
void gen_rseg() {
rseg.resize(n);
vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && arr[i] >= arr[st.back()]) {
add(st.back(), i);
st.pop_back();
}
if (!st.empty()) {
add(st.back(), i);
}
st.push_back(i);
}
}
void make_rseg() {
vector<pair<int, int> > new_rseg;
for (int a = 0; a < n; ++a) {
new_rseg.clear();
int last_sum = 0;
sort(all(rseg[a]));
for (auto pp : rseg[a]) {
if (pp.second > last_sum) {
new_rseg.push_back(pp);
last_sum = pp.second;
}
}
rseg[a] = new_rseg;
// cerr << "new_rseg " << a << endl;
// for (auto pp : rseg[a]) {
// cerr << pp.first << " " << pp.second << endl;
// }
}
}
void get_updates() {
arr_rmq.build(arr, n);
sum_update.resize(n);
val_update.resize(n);
for (int a = 0; a < n; ++a) {
int last_val = 0;
for (int i = 0; i < (int)rseg[a].size(); ++i) {
auto pp = rseg[a][i];
sum_update[pp.first].emplace_back(a, pp.second);
if (i) {
int new_val = rseg[a][i - 1].second + arr_rmq.get(rseg[a][i - 1].first, pp.first - 1);
if (chkmax(last_val, new_val)) {
val_update[pp.first].emplace_back(a, new_val);
}
}
}
}
}
void super_scanline() {
q_rmq.init(n);
T.init(n);
for (int i = 0; i < n; ++i) {
for (auto pp : val_update[i]) {
q_rmq.update(pp.first, pp.second);
}
for (auto pp : sum_update[i]) {
T.change_val(pp.first, 0);
T.change_sum(pp.first, pp.second);
}
T.chkmax_val(arr[i]);
for (auto pp : lq[i]) {
// cerr << "get " << pp.second << endl;
int res1 = q_rmq.get(pp.first, n - 1);
int res2 = T.get(pp.first, n - 1);
ans[pp.second] = max(res1, res2);
}
}
}
void print_ans() {
for (int i = 0; i < m; ++i) {
writeInt(ans[i], '\n');
}
}
signed main() {
fast_io();
read();
gen_rseg();
make_rseg();
get_updates();
super_scanline();
print_ans();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| 11 |
Correct |
239 ms |
14776 KB |
Output is correct |
| 12 |
Correct |
232 ms |
14584 KB |
Output is correct |
| 13 |
Correct |
209 ms |
14708 KB |
Output is correct |
| 14 |
Correct |
241 ms |
14740 KB |
Output is correct |
| 15 |
Correct |
236 ms |
14712 KB |
Output is correct |
| 16 |
Correct |
244 ms |
14080 KB |
Output is correct |
| 17 |
Correct |
239 ms |
13944 KB |
Output is correct |
| 18 |
Correct |
241 ms |
14200 KB |
Output is correct |
| 19 |
Correct |
236 ms |
14584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
810 ms |
58488 KB |
Output is correct |
| 2 |
Correct |
435 ms |
52344 KB |
Output is correct |
| 3 |
Correct |
338 ms |
52292 KB |
Output is correct |
| 4 |
Correct |
803 ms |
58524 KB |
Output is correct |
| 5 |
Correct |
814 ms |
58488 KB |
Output is correct |
| 6 |
Correct |
806 ms |
58360 KB |
Output is correct |
| 7 |
Correct |
819 ms |
58616 KB |
Output is correct |
| 8 |
Correct |
819 ms |
58496 KB |
Output is correct |
| 9 |
Correct |
832 ms |
58616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| 11 |
Correct |
239 ms |
14776 KB |
Output is correct |
| 12 |
Correct |
232 ms |
14584 KB |
Output is correct |
| 13 |
Correct |
209 ms |
14708 KB |
Output is correct |
| 14 |
Correct |
241 ms |
14740 KB |
Output is correct |
| 15 |
Correct |
236 ms |
14712 KB |
Output is correct |
| 16 |
Correct |
244 ms |
14080 KB |
Output is correct |
| 17 |
Correct |
239 ms |
13944 KB |
Output is correct |
| 18 |
Correct |
241 ms |
14200 KB |
Output is correct |
| 19 |
Correct |
236 ms |
14584 KB |
Output is correct |
| 20 |
Correct |
810 ms |
58488 KB |
Output is correct |
| 21 |
Correct |
435 ms |
52344 KB |
Output is correct |
| 22 |
Correct |
338 ms |
52292 KB |
Output is correct |
| 23 |
Correct |
803 ms |
58524 KB |
Output is correct |
| 24 |
Correct |
814 ms |
58488 KB |
Output is correct |
| 25 |
Correct |
806 ms |
58360 KB |
Output is correct |
| 26 |
Correct |
819 ms |
58616 KB |
Output is correct |
| 27 |
Correct |
819 ms |
58496 KB |
Output is correct |
| 28 |
Correct |
832 ms |
58616 KB |
Output is correct |
| 29 |
Runtime error |
308 ms |
118392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 30 |
Halted |
0 ms |
0 KB |
- |
