Submission #928421

#	Time	Username	Problem	Language	Result	Execution time	Memory
928421		vjudge1	Triple Jump (JOI19_jumps)	C++17	100 / 100	973 ms	124028 KiB

jumps

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 5e5 + 2;
ll a[N + 2];
int b[N + 2];
int  c[N + 2];
vector < pair < int , int >  > query[N  + 2];
ll st[4 * N + 2];
ll mx1[4 * N + 2];
ll mx2[4 * N + 2];
vector < int > d[N + 2];
vector < int >  f[N + 2];
void update(int id , int l , int r , int post , ll val ){
    if(l > post || r < post){
        return;
    }
    if(l == r){
        mx1[id] =  max(mx1[id],a[l]);
        mx2[id] = max(mx2[id],val);
        st[id] = mx1[id] + mx2[id];
        return ;
    }
    int mid = (l + r) / 2;
    update(id * 2 , l , mid , post , val);
    update(id * 2 + 1 , mid + 1 , r  , post , val);
    st[id] = max({st[id * 2 + 1] , st[id * 2] , mx2[id * 2] + mx1[id * 2 + 1]});
    mx1[id] = max(mx1[id * 2] , mx1[id * 2 + 1]);
    mx2[id ] =  max(mx2[id * 2 + 1] , mx2[id * 2]);
}
pair < ll , pair <ll , ll > > get(int id , int l , int r ,int u , int v ){
    if(l > v || r < u)return {0 , {0 , 0 }};
    pair < ll , pair <ll , ll > >  ans;
    if(u <= l && r <= v){
        return {st[id] , {mx1[id], mx2[id]}};
    }
    int mid =(l + r) /2;
    auto[max1 , cur1] = get(id  * 2 , l , mid ,u ,v);
    auto[max2 , cur2] = get(id * 2 + 1 , mid + 1 , r ,u ,v);
    ans.first = max({max1 , max2 , cur1.second + cur2.first});
    ans.second.first = max(cur2.first, cur1.first);
    ans.second.second = max(cur2.second ,cur1.second);
    return ans;
}
ll res[N + 2];
void solve() {
    int n  ,q ;
    cin >> n ;
    stack< int > q1;
    stack< int > q2;
    for(int i = 1 ;i <= n ;i ++){
        cin >> a[i];
    }
    q1.push(n + 1);
    q2.push(n + 2);
    a[n + 1] = INT64_MAX;
    a[n + 2] = INT64_MIN;
    for(int i = n ; i >= 1 ; i --){
        while(a[q1.top()] <  a[i])q1.pop();
        while(a[q2.top()] >= a[i])q2.pop();
        b[i] = q1.top();
        c[i] = q2.top();
        q1.push(i);
        q2.push(i);
    }
    while(q1.size())q1.pop();
    while(q2.size())q2.pop();
    for(int i = 1; i <= n ;i ++){
        while(q1.size() && a[q1.top()] <  a[i])q1.pop();
        while(q2.size()&& a[q2.top()] >= a[i])q2.pop();
        if(q1.size())d[q1.top()].push_back(i);
        if(q2.size())f[q2.top()].push_back(i);
        q1.push(i);
        q2.push(i);
    }
    cin >> q;
    for(int i = 1; i <= q; i ++){
        int l , r;
        cin >> l >> r;
        query[l].push_back({r , i});
    }
    for(int i = n ;i >= 1 ;i --){
        update(1 , 1 , n , 2 * b[i] - i , a[i] + a[b[i]]);
        update(1 , 1 , n , 2 * c[i] - i , a[i] + a[c[i]]);
        for(auto vl : d[i]){
             update(1 , 1 , n , 2 * vl - i , a[i] + a[vl]);
        }
        for(auto vl : f[i]){
             update(1 , 1 , n , 2 * vl - i , a[i] + a[vl]);
        }
        for(auto[r , id] : query[i]){
            res[id] = get(1 , 1 , n , i , r).first;
        }
    }
    for(int i = 1; i <= q; i ++)cout << res[i] << "\n";

    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    #define _ "digit."
    if (fopen(_ "inp", "r")) {
        freopen(_ "inp", "r", stdin);
        freopen(_ "out", "w", stdout);
    }
    
    solve();
}

Compilation message (stderr)

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

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