Submission #260753

#	Time	Username	Problem	Language	Result	Execution time	Memory
260753		limabeans	Triple Jump (JOI19_jumps)	C++17	100 / 100	1215 ms	99192 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





const int inf = 1e9;

struct node {
    int ab,c,abc;
    node() {
	ab=c=abc=-inf;
    }
    node(int _ab, int _c, int _abc) : ab(_ab), c(_c), abc(_abc) {}
};

struct segtree {
    node merge(node x, node y) {
	return { max(x.ab,y.ab), max(x.c,y.c), max({x.abc,y.abc,x.ab+y.c}) };
	return x;
    }
    int n;
    vector<node> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, int val, int stat) {
	if (tl == tr) {
	    if (stat==0) {
		t[v].ab=max(t[v].ab, val);
	    } else {
		t[v].c=max(t[v].c, val);
	    }
	    t[v].abc = max(t[v].abc, t[v].ab + t[v].c);
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,val,stat);
	    } else {
		upd(2*v+1,tm+1,tr,i,val,stat);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    node qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return node();
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};

const int maxn = 5e5+10;



int n;
int A[maxn];
vector<int> B[maxn];

int q;
int ans[maxn];
vector<pair<int,int>> Q[maxn]; //(r,i)
segtree tree;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n;
    tree.init(n+10);
    
    for (int i=1; i<=n; i++) {
	cin>>A[i];
	tree.upd(1,1,n,i,A[i],1);
    }
    

    cin>>q;
    for (int i=0; i<q; i++) {
	int l,r;
	cin>>l>>r;
	Q[l].push_back({r,i});
    }

    stack<int> stk;
    for (int i=1; i<=n; i++) {
	while (!stk.empty() && A[stk.top()] <= A[i]) {
	    B[stk.top()].push_back(i);
	    stk.pop();
	}
	if (!stk.empty()) {
	    B[stk.top()].push_back(i);
	}
	stk.push(i);
    }

    for (int a=n; a>=1; a--) {
	for (int b: B[a]) {
	    int c = b+(b-a);
	    if (c <= n) {
		tree.upd(1,1,n,c,A[a]+A[b],0);
	    }
	}
	for (auto qq: Q[a]) {
	    int idx = qq.second;
	    int r = qq.first;

	    ans[idx] = tree.qry(1,1,n,a,r).abc;
	}
    }

    for (int i=0; i<q; i++) {
	cout<<ans[i]<<"\n";
    }
    
    return 0;
}

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