| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1275626 | monaxia | 3단 점프 (JOI19_jumps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
using namespace std;
// using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = 1e9 + 7;
constexpr ull Mod2 = 1 + 7 * 17 * (1 << 23);
constexpr ull sqr = 320;
constexpr ld eps = 1e-9;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;}
ll st[800005], lazy[800005], st2[800005];
ll a[800005];
void build(int idx, int l, int r, ll a[]){
if(l == r){
st2[idx] = a[l];
st[idx] = a[l];
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid, a);
build(idx << 1 | 1, mid + 1, r, a);
st2[idx] = max(st2[idx << 1], st2[idx << 1 | 1]);
st[idx] = st2[idx];
}
void update(int idx, int l, int r, int u, int v, ll val){
if(v < u) return;
if(lazy[idx] != 0){
st[idx] = max(st[idx], st2[idx] + lazy[idx]);
if(l != r){
lazy[idx << 1] = max(lazy[idx << 1], lazy[idx]);
lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], lazy[idx]);
}
lazy[idx] = 0;
}
if(v < l || r < u) return;
if(u <= l && r <= v){
st[idx] = max(st[idx], val + st2[idx]);
if(l != r){
lazy[idx << 1] = max(lazy[idx << 1], val);
lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], val);
}
return;
}
int mid = (l + r) >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
st[idx] = max(st[idx << 1], st[idx << 1 | 1]);
}
int query(int idx, int l, int r, int u, int v){
if(v < u) return 0;
if(lazy[idx] != 0){
st[idx] = max(st[idx], st2[idx] + lazy[idx]);
if(l != r){
lazy[idx << 1] = max(lazy[idx << 1], lazy[idx]);
lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], lazy[idx]);
}
lazy[idx] = 0;
}
if(v < l || r < u) return 0;
if(u <= l && r <= v) {
return st[idx];
}
int mid = (l + r) >> 1;
return max(query(idx << 1, l, mid, u, v), query(idx << 1 | 1, mid + 1, r, u, v));
}
void solve(){
memset(st, 0, sizeof(st));
memset(lazy, 0, sizeof(st));
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
vector <ll> rr[n + 1];
stack <int> stt;
for(int i = 1; i <= n; i ++){
while(!stt.empty()){
rr[stt.top()].pb(i);
if(a[stt.top()] > a[i]) break;
stt.pop();
}
stt.push(i);
}
build(1, 1, n, a);
vector <pair <int, int>> quer[n + 1];
int Q;
cin >> Q;
ll ans[q + 1];
for(int i = 1; i <= Q; i ++){
int l, r;
cin >> l >> r;
quer[l].pb({r, i});
}
for(int i = n; i >= 1; i --){
for(auto& x : rr[i]) {
update(1, 1, n, 2 * x - i, n, a[i] + a[x]);
// cout << i << " " << x << " " << a[i] + a[x] << ": " << 2 * x - i << "->" << n << "\n";
}
for(auto& x : quer[i]) ans[x.sc] = query(1, 1, n, i, x.fr);
}
for(int i = 1; i <= Q; i ++) cout << ans[i] << '\n';
}
int main(){
// cout << 1; return 0;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("TABLE.inp", "r")){
freopen("TABLE.inp", "r", stdin);
freopen("TABLE.out", "w", stdout);
}
ll t = 1;
// for if the problem requires multitest
// cin >> t;
while(t --){
solve();
cout << "\n";
}
cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
// Whose eyes are those eyes?