Submission #943593

#	Time	Username	Problem	Language	Result	Execution time	Memory
943593		PlayVoltz	Triple Jump (JOI19_jumps)	C++17	100 / 100	1282 ms	152304 KiB

jumps

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
ll const INF = 1e9;

vector<int> vect;

struct node{
 
    int s, e, m; 
    ll aval, summ, pv, lazy;
    node *l, *r; 
	node (int S, int E)
	{ 
       s = S, e = E, m = (s+e)/2;
       summ = pv = -INF;
       if (s==e) {aval = vect[s]; return;}
       l = new node(s, m); 
	   r = new node(m+1, e);
	   aval = max(l->aval, r->aval);
	   lazy = -INF;
 
    }
 
	void propogate()
	{
	   if (lazy==-INF) return;
	   if (s!=e)
	   {
		   l->lazy = max(l->lazy, lazy);
		   r->lazy = max(r->lazy, lazy);
           l->pv= max(l->pv, lazy);
           l->summ = max(l->summ, l->aval + lazy);
           r->pv= max(r->pv, lazy);
           r->summ = max(r->summ, r->aval + lazy);
	   }
	   lazy = -INF;
    }
    
	void update(int S, int E, ll V)
	{ 
		if (S>E)return;
	   propogate();
       if(s==S && e==E) 
       {
         lazy = max(lazy, V);
         pv= max(pv, V);
         summ = max(summ, aval + pv);
       }
       else{ 
           propogate();
           if(E <= m) l->update(S, E, V); 
           else if (m < S) r->update(S, E, V); 
           else l->update(S, m, V),r->update(m+1, E, V);
           l->propogate(),r->propogate();
		   summ = max(l->summ, r->summ);
          
       }
    }
	ll query(int S, int E)
	{
	   propogate(); 
       if(s == S && e == E) return summ; 
       propogate();
       if(E <= m) return l->query(S, E); 
       else if(S >= m+1) return r->query(S, E); 
       else return max(l->query(S, m), r->query(m+1, E)); 
   }
 
} *st;

int32_t main(){
	int n, q, a, b;
	cin>>n;
	vect.resize(n+1);
	vector<vector<pii> > queries(n+1);
	for (int i=1; i<=n; ++i)cin>>vect[i];
	cin>>q;
	vector<int> ans(q);
	vector<vector<int> > next(n+1);
	st = new node(1, n);
	for (int i=0; i<q; ++i){
		cin>>a>>b;
		queries[a].pb(mp(b, i));
	}
	stack<int> s;
	for (int i=1; i<=n; ++i){
		while (!s.empty()&&vect[s.top()]<=vect[i])next[s.top()].pb(i), s.pop();
		s.push(i);
	}
	while (!s.empty())s.pop();
	for (int i=n; i>=1; --i){
		while (!s.empty()&&vect[s.top()]<=vect[i])next[i].pb(s.top()), s.pop();
		s.push(i);
	}
	for (int i=n; i>=1; --i){
		for (auto c:next[i])st->update(2*c-i, n, vect[i]+vect[c]);
		for (auto c:queries[i])ans[c.se]=st->query(i, c.fi);
	}
	for (auto a:ans)cout<<a<<"\n";
}

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