Submission #1255823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255823		mngoc._.	Triple Jump (JOI19_jumps)	C++20	0 / 100	18 ms	10056 KiB

jumps

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 5e5 + 5;
pii st[4 * N];
int a[N];
struct query{
	int l , r , idx;
};
int res[N];
vector<query> queries;
int n , q;
void build(int idx , int l , int r){
	if(l == r){
		st[idx].first = a[l];
		st[idx].second = l;
		return;
	}
	int mid = (l + r) / 2;
	build(2 * idx , l , mid);
	build(2 * idx + 1 , mid + 1 , r);
	if(st[2 * idx].first >= st[2 * idx + 1].first) st[idx] = st[2 * idx];
	else st[idx] = st[2 * idx + 1];
	
}

void update(int idx , int l , int r , int pos , int val){
	if(l > pos || r < pos) return;
	if(l == r){
		st[idx].first = val;
		return;
	}
	int mid = (l + r) / 2;
	update(2 * idx , l , mid , pos , val);
	update(2 * idx + 1 , mid + 1 , r , pos , val);
	if(st[2 * idx].first >= st[2 * idx + 1].first) st[idx] = st[2 * idx];
	else st[idx] = st[2 * idx + 1];
}

pii get(int idx , int l , int r , int u , int v){
	if(l > v || r < u) return {0 , -1};
	if(u <= l && r <= v) return st[idx];
	int mid = (l + r) / 2;
	pii t1 = get(2 * idx , l , mid  , u , v);
	pii t2 = get(2 * idx + 1 , mid + 1 , r , u , v);
	if(t1.first >= t2.first) return t1;
	else return t2;
}


void DnC(int l , int r , vector<query> qq){
	if(r - l + 1 < 3 || qq.size() == 0) return;
	int mid = (l + r) / 2;
	vector<query> tmp , qleft , qright; 
	for(auto x : qq){
		if(x.r < mid) qleft.push_back(x);
		else if(x.l > mid) qright.push_back(x);
		else tmp.push_back(x);
	}
	for(auto x : tmp){
		pii u = get(1 , 1  , n , x.l , mid);
		update(1, 1 , n , u.second , 0LL);
		pii v = get(1 , 1 , n , x.l , mid);
		pii z = get(1 , 1 , n , mid + 1 , x.r);
		res[x.idx] = u.first + v.first + z.first;

		update(1 , 1 , n , u.second , u.first);
		u = get(1 , 1 , n , x.l , mid);
		update(1 , 1 , n , u.second , 0);
		v = get(1 , 1 , n , x.l , mid);
		update(1 , 1 , n , v.second , 0);
		z = get(1 , 1 , n , x.l , mid);
		if(mid - x.l + 1 >= 3) res[x.idx] = max(res[x.idx] , u.first + v.first + z.first);

		update(1 , 1,  n , u.second , u.first);
		update(1 , 1 , n , v.second , v.first);
		u = get(1 , 1 , n , mid + 1 , x.r);
		update(1 , 1 , n , u.second , 0);
		v = get(1 , 1 , n , mid + 1 , x.r);
		update(1 , 1 , n , v.second , 0);
		z = get(1 , 1 , n , mid + 1 , x.r);
		if(x.r - mid + 1 >= 3) res[x.idx] = max(res[x.idx] ,u.first + v.first + z.first);

		update(1 , 1,  n , u.second , u.first);
		update(1 , 1 , n , v.second , v.first);
	    u = get(1 , 1 , n , mid + 1 , x.r);
		update(1 , 1 , n , u.second , 0);
		v = get(1 , 1 , n , mid + 1 , x.r);
		update(1 , 1 , n , v.second , 0);
		int dist = max(v.second , u.second) - min(v.second , u.second);
		z = get(1 , 1 , n , max(min(v.second , u.second) - dist , x.l) , max(min(v.second , u.second) - 1 , x.l));
		res[x.idx] = max(res[x.idx] ,u.first + v.first + z.first);
        update(1 , 1,  n , u.second , u.first);
		update(1 , 1 , n , v.second , v.first);
        		
		

	}
	DnC(l , mid - 1 , qleft);
	DnC(mid + 1 , r , qright);
}

void solve(void){
	cin >> n; for(int i = 1; i  <= n ; i++) cin >> a[i];
	cin >> q;
	for(int i = 1 ; i <= q;  i++){
		int l , r; cin >> l >> r;
		queries.push_back({l , r , i});
	}
	build(1 , 1 , n);
	DnC(1 , n , queries);
	for(int i = 1 ; i <= q ; i++){
		cout << res[i] << endl;
	}
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solve();
	return 0;
}

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