oj.uz

Submission #1118756

# Submission time Handle Problem Language Result Execution time Memory
1118756 2024-11-26T05:43:33 Z Math4Life2020 Triple Jump (JOI19_jumps) C++17
27 / 100
 215 ms 89980 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

ll N,Q; const ll Nm = 524288; const ll E = 19;
const ll INF = 2e18;
ll rmqV[Nm][E+1];
vector<ll> A,L,R;

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

void initRMQ() {
	for (ll i=0;i<N;i++) {
		rmqV[i][0]=A[i];
	}
	for (ll j=1;j<=E;j++) {
		for (ll i=0;i<=(Nm-(1LL<<j));i++) { //i=Nm-2^j means Nm-2^j to Nm-2^(j-1)-1 and Nm-2^(j-1) to Nm-1
			rmqV[i][j]=max(rmqV[i][j-1],rmqV[i+(1LL<<(j-1))][j-1]);
		} 
	}
}

ll rmq(ll a, ll b) {
	if (b<a) {
		return (-INF);
	}
	ll l = l2(b-a+1);
	return max(rmqV[a][l],rmqV[b-(1LL<<l)+1][l]);
}

ll solve3(ll l, ll r) {
	ll ans = -INF;
	vector<pii> vat;
	for (ll i=l;i<=r;i++) {
		vat.push_back({A[i],i});
	}
	sort(vat.rbegin(),vat.rend());
	for (ll k=0;k<min(30LL,r-l+1);k++) {
		ll i = vat[k].second;
		ll vi = A[i];
		//c=i
		for (ll b=l;b<i;b++) {
			ans = max(ans,vi+A[b]+rmq(max(l,2*b-i),b-1));
		}
		//b=i
		for (ll a=l;a<i;a++) {
			ans = max(ans,vi+A[a]+rmq(2*i-a,r));
		}
		//a=i
		for (ll b=(i+1);b<=r;b++) {
			ans = max(ans,vi+A[b]+rmq(2*b-i,r));
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	for (ll i=0;i<N;i++) {
		ll a1; cin >> a1;
		A.push_back(a1);
	}
	initRMQ();
	cin >> Q;
	for (ll i=0;i<Q;i++) {
		ll l1,r1; cin >> l1 >> r1;
		l1--; r1--;
		L.push_back(l1);
		R.push_back(r1);
	}
	// if (Q==1 && L[0]==0 && R[0]==(N-1)) {
	// 	solve3();
	// }
	for (ll q=0;q<Q;q++) {
		cout << solve3(L[q],R[q]);
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 82520 KB Output is correct
2 Incorrect 112 ms 82300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 82520 KB Output is correct
2 Incorrect 112 ms 82300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 89980 KB Output is correct
2 Correct 190 ms 89952 KB Output is correct
3 Correct 151 ms 89968 KB Output is correct
4 Correct 197 ms 89928 KB Output is correct
5 Correct 198 ms 89928 KB Output is correct
6 Correct 199 ms 89440 KB Output is correct
7 Correct 213 ms 89188 KB Output is correct
8 Correct 215 ms 89100 KB Output is correct
9 Correct 175 ms 89460 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 82520 KB Output is correct
2 Incorrect 112 ms 82300 KB Output isn't correct
3 Halted 0 ms 0 KB -