Submission #926161

#	Time	Username	Problem	Language	Result	Execution time	Memory
926161		velislavgarkov	Triple Jump (JOI19_jumps)	C++14	100 / 100	825 ms	55728 KiB

jumps

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXN=5e5+10;
#define endl '\n'
struct Query {
    int l;
    int r;
    int ind;
    bool friend operator < (Query a, Query b) {
        return a.l>b.l;
    }
};
struct Jump {
    int a;
    int b;
    int sum;
    bool friend operator < (Jump a, Jump b) {
        return a.a>b.a;
    }
};
Query que[MAXN];
vector <Jump> v;
stack <int> st;
int tree[4*MAXN], lazy[4*MAXN], mx[4*MAXN];
int a[MAXN], ans[MAXN];
void build_tree(int node, int l, int r) {
    lazy[node]=0;
    if (l==r) {
        tree[node]=a[l];
        mx[node]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node]=max(tree[node*2],tree[node*2+1]);
    mx[node]=tree[node];
}
void add_lazy(int node, int ch) {
    if (ch<=lazy[node]) return;
    lazy[node]=ch;
    tree[node]=max(tree[node],mx[node]+ch);
}
void push_lazy(int node, int l, int r) {
    if (l!=r) {
        add_lazy(node*2,lazy[node]);
        add_lazy(node*2+1,lazy[node]);
    }
    lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr, int ch) {
    if (ql>r || qr<l) return;
    push_lazy(node,l,r);
    if (l>=ql && r<=qr) {
        add_lazy(node,ch);
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr,ch);
    update(node*2+1,mid+1,r,ql,qr,ch);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return 0;
    push_lazy(node,l,r);
    if (l>=ql && r<=qr) {
        //cout << l << ' ' << r << ' ' << tree[node] << endl;
        return tree[node];
    }
    int mid=(l+r)/2;
    return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        while (!st.empty() && a[i]>a[st.top()]) st.pop();
        if (!st.empty()) v.push_back({st.top(),i,a[i]+a[st.top()]});
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i=n;i>=1;i--) {
        while (!st.empty() && a[i]>a[st.top()]) st.pop();
        if (!st.empty()) v.push_back({i,st.top(),a[i]+a[st.top()]});
        st.push(i);
    }
    sort(v.begin(),v.end());
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> que[i].l >> que[i].r;
        que[i].ind=i;
    }
    sort(que,que+q);
    int curq, curv;
    curq=curv=0;
    build_tree(1,1,n);
    for (int i=n-2;i>=1;i--) {
        while (curv<v.size() && v[curv].a>=i) {
            int gr=v[curv].b*2-v[curv].a;
            if (gr<=n) {
                //cout << v[curv].a << ' ' << v[curv].b << ' ' << gr << endl;
                update(1,1,n,gr,n,v[curv].sum);
            }
            curv++;
        }
        while (curq<q && que[curq].l==i) {
            ans[que[curq].ind]=query(1,1,n,que[curq].l,que[curq].r);
            curq++;
        }
        if (curq==q) break;
    }
    for (int i=0;i<q;i++) cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Jump>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while (curv<v.size() && v[curv].a>=i) {
      |                ~~~~^~~~~~~~~

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