Submission #296412

#	Time	Username	Problem	Language	Result	Execution time	Memory
296412		BeanZ	Triple Jump (JOI19_jumps)	C++14	100 / 100	1591 ms	114232 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 5e5 + 5;
struct viet{
        ll a, b, v;
};
viet st[N * 4];
ll a[N], ans[N];
vector<pair<ll, ll>> mem[N], qr[N];
void Init(ll k, ll l, ll r){
        if (l == r){
                st[k].a = a[l];
                return;
        }
        ll mid = (l + r) >> 1;
        Init(k << 1, l, mid);
        Init(k << 1 | 1, mid + 1, r);
        st[k].a = max(st[k << 1].a, st[k << 1 | 1].a);
}
void down(ll k){
        st[k << 1].b = max(st[k << 1].b, st[k].b);
        st[k << 1].v = max(st[k << 1].v, st[k << 1].a + st[k << 1].b);
        st[k << 1 | 1].b = max(st[k << 1 | 1].b, st[k].b);
        st[k << 1 | 1].v = max(st[k << 1 | 1].v, st[k << 1 | 1].a + st[k << 1 | 1].b);
}
void upd(ll k, ll l, ll r, ll x, ll y, ll v){
        if (x > r || y < l) return;
        if (l != r) down(k);
        if (x <= l && y >= r){
                st[k].b = max(st[k].b, v);
                st[k].v = max(st[k].v, st[k].b + st[k].a);
                return;
        }
        ll mid = (l + r) >> 1;
        upd(k << 1, l, mid, x, y, v);
        upd(k << 1 | 1, mid + 1, r, x, y, v);
        st[k].v = max(st[k << 1].v, st[k << 1 | 1].v);
}
ll get(ll k, ll l, ll r, ll x, ll y){
        if (x > r || y < l) return 0;
        if (l != r) down(k);
        if (x <= l && y >= r) return st[k].v;
        ll mid = (l + r) >> 1;
        return max(get(k << 1, l, mid, x, y), get(k << 1 | 1, mid + 1, r, x, y));
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("balance.in", "r")){
                freopen("balance.in", "r", stdin);
                freopen("balance.out", "w", stdout);
        }
        ll n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        stack<ll> s;
        for (int i = 1; i <= n; i++){
                while (s.size()){
                        if (a[s.top()] <= a[i]){
                                ll k = 2 * i - s.top();
                                if (k <= n) mem[s.top()].push_back({k, a[i] + a[s.top()]});
                        } else break;
                        s.pop();
                }
                if (s.size()){
                        ll k = 2 * i - s.top();
                        if (k <= n) mem[s.top()].push_back({k, a[i] + a[s.top()]});
                }
                s.push(i);
        }
        ll q;
        cin >> q;
        for (int i = 1; i <= q; i++){
                ll l, r;
                cin >> l >> r;
                qr[l].push_back({r, i});
        }
        Init(1, 1, n);
        for (int i = n; i >= 1; i--){
                for (auto j : mem[i]){
                        upd(1, 1, n, j.first, n, j.second);
                }
                for (auto j : qr[i]){
                        ans[j.second] = get(1, 1, n, i, j.first);
                }
        }
        for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}
/*
*/

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:54:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 |                 freopen("balance.in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:55:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |                 freopen("balance.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54