Submission #1255837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255837		mngoc._.	Triple Jump (JOI19_jumps)	C++20	0 / 100	16 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;

bool cmp(const pii& x, const pii& y){
	return x.second < y.second;
}
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;
}
vector<pii> get2(int L, int R, int K){
    vector<pii> ans;
    if(L > R) return ans;
    vector<pii> m; 
    for(int it = 0; it < K; ++it){
        pii t = get(1, 1, n, L, R);
        if(t.second == -1 || t.first == 0) break;
        ans.emplace_back(t.first, t.second);
        m.emplace_back(t.second, t.first);
        update(1, 1, n, t.second, 0);
    }
    for(auto p : m){
        update(1, 1, n, p.first, p.second);
    }
    return ans;
}

void met(const pii& A, const pii& B, const pii& C, int ql){
    if(A.second <= 0 || B.second <= 0 || C.second <= 0) return;
    vector<pii> tmp;
    tmp.push_back(A);
    tmp.push_back(B);
    tmp.push_back(C);
    sort(tmp.begin(), tmp.end(), cmp);
    int a_val = tmp[0].first, a_idx = tmp[0].second;
    int b_val = tmp[1].first, b_idx = tmp[1].second;
    int c_val = tmp[2].first, c_idx = tmp[2].second;
    if(!(a_idx < b_idx && b_idx < c_idx)) return;
    if((b_idx - a_idx) <= (c_idx - b_idx)){
        res[ql] = max(res[ql], (int)(a_val + b_val + c_val));
    }
}

void DnC(int l, int r, vector<query> qq){
    if(r - l + 1 < 3 || qq.empty()) return;
    int mid = (l + r) / 2;
    vector<query> qleft, qright , tmp;
    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){
        auto L = get2(x.l, mid, 3);
        auto R = get2(mid+1, x.r, 3);
        if(L.size() >= 3){
            for(int i = 0; i < L.size(); ++i)
            for(int j = i+1; j < L.size(); ++j)
            for(int k = j+1; k < L.size(); ++k)
            met(L[i], L[j], L[k], x.idx);
        }
        if(R.size() >= 3){
            for(int i = 0; i < R.size(); ++i)
            for(int j = i+1; j < R.size(); ++j)
            for(int k = j+1; k < R.size(); ++k)
            met(R[i], R[j], R[k], x.idx);
        }
        for(int i = 0; i < L.size(); ++i)
        for(int j = 0; j < L.size(); ++j){
            if(i == j) continue;
            if(L[i].second == L[j].second) continue;
            for(int k = 0; k < R.size(); ++k){
                met(L[i], L[j], R[k], x.idx);
            }
        }
        for(int i = 0; i < L.size(); ++i)
        for(int j = 0; j < R.size(); ++j)
        for(int k = 0; k < R.size(); ++k){
            if(j == k) continue;
            if(R[j].second == R[k].second) continue;
            met(L[i], R[j], R[k], x.idx);
        }
    }
    DnC(l , mid, 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