Submission #372532

#	Time	Username	Problem	Language	Result	Execution time	Memory
372532		erfanmir	Triple Jump (JOI19_jumps)	C++17	100 / 100	1388 ms	87992 KiB

jumps

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

struct node{
    int x;
    int y;
    int res;
};

node mrg(node A, node B){
    node C;
    C.res = max({A.res, B.res, A.x + B.y});
    C.x = max(A.x, B.x);
    C.y = max(A.y, B.y);
    return C;
}

const int MAXN = 5e5 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int a[MAXN], n, q, ans[MAXN];
node seg[MAXN * 4];
vector<int> pre[MAXN], st;
vector<pii> que[MAXN];

void upd(int ind, int val1, int val2, int s = 0, int e = n, int v = 1){
    if(e - s < 2){
        seg[v].x = max(seg[v].x, val1);
        seg[v].y = max(seg[v].y, val2);
        seg[v].res = max(seg[v].res, seg[v].x + seg[v].y);
        return;
    }
    int mid = (s + e) / 2;
    if(ind < mid){
        upd(ind, val1, val2, s, mid, lc(v));
    }
    else{
        upd(ind, val1, val2, mid, e, rc(v));
    }
    seg[v] = mrg(seg[lc(v)], seg[rc(v)]);
}

node get(int l, int r, int s = 0, int e = n, int v = 1){
    if(r <= s || e <= l){
        return {0, 0, 0};
    }
    if(l <= s && e <= r){
        return seg[v];
    }
    int mid = (s + e) / 2;
    return mrg(get(l, r, s, mid, lc(v)), get(l, r, mid, e, rc(v)));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", a + i);
    }
    for(int i = 0; i < n; i++){
        while((int)st.size() && a[i] > a[st.back()]){
            pre[st.back()].push_back(i);
            st.pop_back();
        }
        if((int)st.size()){
            pre[st.back()].push_back(i);
        }
        st.push_back(i);
    }
    scanf("%d", &q);
    for(int i = 0; i < q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        l--;
        que[l].push_back(mp(r, i));
    }

    for(int i = n - 1; ~i; i--){
        upd(i, 0, a[i]);
        for(auto u : pre[i]){
            int p = 2 * u - i;
            if(p < n){
                upd(p, a[i] + a[u], 0);
            }
        }
        for(auto u : que[i]){
            node w = get(i, u.F);
            ans[u.S] = w.res;
        }
    }

    for(int i = 0; i < q; i++){
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

jumps.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
jumps.cpp: In function 'int main()':
jumps.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |         scanf("%d", a + i);
      |         ~~~~~^~~~~~~~~~~~~
jumps.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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