Submission #367745

#	Time	Username	Problem	Language	Result	Execution time	Memory
367745		BartolM	Triple Jump (JOI19_jumps)	C++17	100 / 100	1425 ms	87788 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=5e5+5;
const int OFF=(1<<19);

struct Node{
    int ab, c, res;
    Node (int ab_=-INF, int c_=-INF, int res_=-INF) {
        ab=ab_; c=c_; res=res_;
    }
};

int n, q;
int p[N], sol[N];
vector <pii> que[N];
vector <int> v[N];
vector <int> st;
Node T[2*OFF];
#define DEBUG 0

Node mrg(Node a, Node b) {
    Node ret=Node(max(a.ab, b.ab), max(a.c, b.c), max(a.res, b.res));
    ret.res=max(ret.res, a.ab+b.c);
    return ret;
}

void update(int pos, int val, int fl) {
    if (pos>=n) return;

    pos+=OFF;
    if (fl) T[pos].ab=max(T[pos].ab, val);
    else T[pos].c=max(T[pos].c, val);
    T[pos].res=max(T[pos].res, T[pos].ab+T[pos].c);

    pos/=2;
    while (pos) {
        T[pos]=mrg(T[pos*2], T[pos*2+1]);
        pos/=2;
    }
}

Node query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return T[pos];
    if (lo>=b || hi<=a) return Node();
    int mid=(lo+hi)/2;
    return mrg(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
}

void solve() {
    for (int i=0; i<n; ++i) {
        while (st.size() && p[st.back()]<=p[i]) {
            v[st.back()].pb(i);
            st.pop_back();
        }
        if (st.size()) v[st.back()].pb(i);
        st.pb(i);
    }
    #if DEBUG
        for (int i=0; i<n; ++i) {
            for (int r:v[i]) printf("[%d, %d]\n", i, r);
        }
    #endif // DEBUG
    for (int i=n-1; i>=0; --i) {
        update(i, p[i], 0);
        for (int r:v[i]) update(2*r-i, p[i]+p[r], 1);
        for (pii pp:que[i]) sol[pp.Y]=query(i, pp.X+1).res;
    }
    for (int i=0; i<q; ++i) printf("%d\n", sol[i]);
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i) scanf("%d", &p[i]);
    scanf("%d", &q);
    for (int i=0; i<q; ++i) {
        int l, r;
        scanf("%d %d", &l, &r); l--; r--;
        que[l].pb(mp(r, i));
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void load()':
jumps.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:86:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |     for (int i=0; i<n; ++i) scanf("%d", &p[i]);
      |                             ~~~~~^~~~~~~~~~~~~
jumps.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         scanf("%d %d", &l, &r); l--; r--;
      |         ~~~~~^~~~~~~~~~~~~~~~~

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