Submission #1015665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015665		Nurislam	Triple Jump (JOI19_jumps)	C++17	27 / 100	198 ms	75204 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long

const int N = 5e5+5, inf = 1e16, mod = 1e9+7;
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
struct node{
	int ans, ab, c;
	
	node operator +(node nw){
		chmax(ans, nw.ans);
		chmax(ab, nw.ab);
		chmax(c, nw.c);
		return *this;
	}
};
struct segtree{
	vector<node> t;
	vector<int> b;
	segtree(){
		t.resize(N*4);
		b.resize(N*4, 0);
	};
	
	void build(int i, int l, int r, vector<int> &a){
		if(l == r){
			t[i] = {a[l], 0ll, a[l]};
			return;
		}
		int m = (l+r)>>1;
		build(i*2, l, m, a);
		build(i*2+1, m+1, r, a);
		t[i] = t[i*2] + t[i*2+1];
	};
	void push(int i, int l, int r){
		if(l!=r){
			chmax(b[i*2],b[i]);
			chmax(b[i*2+1],b[i]);
		}
		chmax(t[i].ab, b[i]);
		chmax(t[i].ans, b[i] + t[i].c);
		b[i] = 0;
		return;
	};
	void upd(int i, int tl, int tr, int l, int r, int val){
		push(i, l, r);
		if(l > tr || r < tl)return;
		if(tl <= l && r <= tr){
			b[i] = val;
			push(i,l,r);
			return;
		}
		int m = (l+r)>>1;
		upd(i*2, tl, tr, l, m, val);
		upd(i*2+1, tl, tr, m+1, r, val);
		t[i] = t[i] + t[i*2];
		t[i] = t[i] + t[i*2+1];
		return;
	};
	
	
	int get(int i, int l, int r, int tl, int tr){
		push(i, l, r);
		if(l > tr || r < tl)return 0ll;
		if(tl <= l && r <= tr)return t[i].ans;
		int m = (l+r)>>1;
		return max(
			get(i*2, l, m, tl, tr),
			get(i*2+1, m+1, r, tl, tr)
			);
	}
	
};
segtree T;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)cin >> a[i];
	T.build(1, 1, n, a);
	vector<vector<pair<int,int>>> qq(n+1);
	int q;cin >> q;
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		qq[l].pb({r, i});
	}
	vector<int> ans(q+1);
	vector<pair<int,int>> cur;
	for(int i = n; i > 0; i--){
		while(cur.size() && cur.back().ff < a[i]){
			int A = i, B = cur.back().ss;
			if(2*B-A <= n)T.upd(1, 2*B-A, n, 1, n, a[A] + a[B]);
			cur.pop_back();
		}
		if(cur.size()){
			int A = i, B = cur.back().ss;
			if(2*B-A <= n)T.upd(1, 2*B-A, n, 1, n, a[A] + a[B]);
		}
		cur.pb({a[i], i});
		
		for(auto j:qq[i]){
			ans[j.ss] = T.get(1, 1, n, i, j.ff);
		}
	}
	for(int i = 0; i < q; i++)cout << ans[i] << '\n';
	
	
}
 
 
 
 
 
 
 
 
 
 
 
 
 

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