Submission #489620

#	Time	Username	Problem	Language	Result	Execution time	Memory
489620		fhvirus	Triple Jump (JOI19_jumps)	C++17	100 / 100	1131 ms	85616 KiB

jumps

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif

const int kN = 500005;
int N, A[kN];
int Q, L[kN], R[kN];

void input(){
	cin >> N;
	for(int i = 1; i <= N; ++i)
		cin >> A[i];
	cin >> Q;
	for(int i = 1; i <= Q; ++i)
		cin >> L[i] >> R[i];
}

int suf[kN];
vector<int> candidate[kN];
vector<int> querys[kN];
int ans[kN];

struct SGT {
	// val1: raw A
	// val2: A + (the modified max)
	int n;
	vector<int> val1, val2, tag;
	[[ gnu::pure ]] int id(int l, int r){ return (l+r) | (l!=r); }
	void build(int l, int r, int *A){
		int i = id(l, r);
		if(l == r){
			val1[i] = A[l];
			return;
		}
		int m = (l+r) / 2;
		build(l, m, A);
		build(m+1, r, A);
		val1[i] = max(val1[id(l, m)], val1[id(m+1, r)]);
	}
	SGT(int nn, int *A):
		n(nn), val1(nn*2+2), val2(nn*2+2, 0), tag(nn*2+2, 0){ build(1, n, A); }
	void upd(int i, int v){
		tag[i] = max(tag[i], v);
		val2[i] = max(val2[i], val1[i] + tag[i]);
	}
	void modify(int l, int r, int ql, int qr, int v){
		int i = id(l, r);
		if(ql <= l and r <= qr){
			upd(i, v);
			return;
		}
		int m = (l+r) / 2;
		upd(id(l, m), tag[i]);
		upd(id(m+1, r), tag[i]);
		tag[i] = 0;
		if(ql <= m) modify(l, m, ql, qr, v);
		if(m < qr) modify(m+1, r, ql, qr, v);
		val2[i] = max(val2[i], val2[id(l, m)]);
		val2[i] = max(val2[i], val2[id(m+1, r)]);
		return;
	}
	int query(int l, int r, int ql, int qr){
		int i = id(l, r);
		if(ql <= l and r <= qr) return val2[i];
		int m = (l+r) / 2;
		upd(id(l, m), tag[i]);
		upd(id(m+1, r), tag[i]);
		tag[i] = 0;
		return max(
			ql <= m ? query(l, m, ql, qr) : 0,
			m < qr ? query(m+1, r, ql, qr) : 0
		);
	}
	void modify(int ql, int qr, int v){ modify(1, n, ql, qr, v); }
	int query(int ql, int qr){ return query(1, n, ql, qr); }
};

void solve(){
	for(int i = N; i >= 1; --i)
		suf[i] = max(suf[i+1], A[i]);

	// make pairs
	vector<int> stk;
	for(int i = 1; i <= N; ++i){
		while(!stk.empty()){
			int j = end(stk)[-1];
			candidate[j].pb(i);
			if(A[j] > A[i]) break;
			stk.pop_back();
		}
		stk.pb(i);
	}
	for(int i = 1; i <= Q; ++i)
		querys[L[i]].pb(i);

	SGT sgt(N, A);
	for(int i = N; i >= 1; --i){
		for(int b: candidate[i])
			if(b+(b-i) <= N)
				sgt.modify(b+(b-i), N, A[i] + A[b]);
		for(int q: querys[i])
			ans[q] = sgt.query(L[q]+2, R[q]);
	}
}

void ouput(){
	for(int i = 1; i <= Q; ++i)
		cout << ans[i] << '\n';
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	input();
	solve();
	ouput();
	return 0;
}

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