| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096972 |
2024-10-05T15:22:58 Z |
Tame |
Triple Jump (JOI19_jumps) |
C++14 |
|
22 ms |
18644 KB |
#include <bits/stdc++.h>
#define pu push
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 500010;
const int inf = (int)1e9+7;
const ll INF = (ll)1e18;
using namespace std;
template<class T1, class T2>
bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}
int nLength, nQuery;
int a[MAX_SIZE];
ll res;
vector<pair<int,int>>queries, tmp;
struct SegmentTree{
int n; vector<pair<int,int>>st;
SegmentTree(int _n=0){
n=_n; st.resize(4*n+5);
}
void build(int id, int l, int r){
if (l==r){
st[id]=make_pair(a[l], l); return;
}
int m = (l+r)>>1;
build(2*id,l,m); build(2*id+1,m+1,r);
st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
}
void update(int id, int l, int r, int v, int k){
if (r<v || v<l) return;
if (l==r){
st[id].fi=k; return;
}
int m = (l+r)>>1;
update(2*id, l, m, v, k); update(2*id+1, m+1, r, v, k);
st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
}
pair<int,int>get(int id, int l, int r, int u, int v){
if (r<u || v<l){
pair<int,int>e = make_pair(-inf, -inf);
return e;
}
if (l>=u && r<=v) return st[id];
int m = (l+r)>>1;
pair<int,int>x=get(2*id, l, m, u, v), y=get(2*id+1, m+1, r, u, v);
if (x.fi > y.fi) return x;
return y;
}
};
SegmentTree IT(MAX_SIZE);
void init(){
cin>>nLength;
for (int i=1; i<=nLength; i++){
cin>>a[i];
}
cin>>nQuery;
for (int i=1; i<=nQuery; i++){
int l, r; cin>>l>>r;
queries.pb(make_pair(l, r));
}
}
bool cmp(const pair<int,int>&x, pair<int,int>&y){
return x.se < y.se;
}
void ilovesunshine(){
init(); IT.build(1, 1, nLength);
for (int i=0; i<(int)queries.size(); i++){
int l=queries[i].fi, r=queries[i].se; res=0; tmp.clear();
pair<int,int>firstPos, secondPos, thirdPos;
tmp.pb(IT.get(1, 1, nLength, l, r)); IT.update(1, 1, nLength, tmp[0].se, -1);
tmp.pb(IT.get(1, 1, nLength, l, r)); IT.update(1, 1, nLength, tmp[1].se, -1);
tmp.pb(IT.get(1, 1, nLength, l, r)); IT.update(1, 1, nLength, tmp[2].se, -1);
sort(tmp.begin(), tmp.end(), cmp);
firstPos = tmp[0]; secondPos = tmp[1]; thirdPos = tmp[2];
// cout<<firstPos.fi<<' '<<firstPos.se<<"\n";
// cout<<secondPos.fi<<' '<<secondPos.se<<"\n";
// cout<<thirdPos.fi<<' '<<thirdPos.se<<"\n";
//CASE 1
if (abs(secondPos.se - firstPos.se) <= abs(thirdPos.se - secondPos.se)){
IT.update(1, 1, nLength, firstPos.se, firstPos.fi);
IT.update(1, 1, nLength, secondPos.se, secondPos.fi);
IT.update(1, 1, nLength, thirdPos.se, thirdPos.fi);
cout<<firstPos.fi + secondPos.fi + thirdPos.fi<<"\n"; continue;
}
pair<int,int>mid;
//CASE 2 (Left 1 And 2)
mid=IT.get(1, 1, nLength, max(l, 2*firstPos.se-secondPos.se), firstPos.se-1);
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + secondPos.fi);
//CASE 3 (Right 1 And 2)
mid=IT.get(1, 1, nLength, secondPos.se+1, min(r, 2*secondPos.se-firstPos.se));
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + secondPos.fi);
//CASE 4 (Left 1 And 3)
mid=IT.get(1, 1, nLength, max(l, 2*firstPos.se-thirdPos.se), firstPos.se-1);
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + thirdPos.fi);
//CASE 5 (Right 1 And 3)
mid=IT.get(1, 1, nLength, thirdPos.se+1, min(r, 2*thirdPos.se-firstPos.se));
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + thirdPos.fi);
//CASE 6 (Left 2 And 3)
mid=IT.get(1, 1, nLength, max(l, 2*secondPos.se-thirdPos.se), secondPos.se-1);
if (mid.fi > 0) maximize(res, mid.fi + secondPos.fi + thirdPos.fi);
//CASE 7 (Right 2 And 3)
mid=IT.get(1, 1, nLength, thirdPos.se+1, min(r, 2*thirdPos.se-secondPos.se));
if (mid.fi > 0) maximize(res, mid.fi + secondPos.fi + thirdPos.fi);
//CASE 8 (Mid 1 And 2)
if (secondPos.se > firstPos.se+1){
mid = IT.get(1, 1, nLength, firstPos.se+1, (secondPos.se+firstPos.se)>>1);
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + secondPos.fi);
}
//CASE 9 (Mid 1 And 3)
if (thirdPos.se > firstPos.se+1){
mid = IT.get(1, 1, nLength, firstPos.se+1, (thirdPos.se+firstPos.se)>>1);
if (mid.fi > 0) maximize(res, mid.fi + firstPos.fi + thirdPos.fi);
}
//CASE 9 (Mid 2 And 3)
if (thirdPos.se > secondPos.se+1){
mid = IT.get(1, 1, nLength, secondPos.se+1, (thirdPos.se+secondPos.se)>>1);
if (mid.fi > 0) maximize(res, mid.fi + secondPos.fi + thirdPos.fi);
}
IT.update(1, 1, nLength, firstPos.se, firstPos.fi);
IT.update(1, 1, nLength, secondPos.se, secondPos.fi);
IT.update(1, 1, nLength, thirdPos.se, thirdPos.fi);
cout<<res<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ilovesunshine();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
18524 KB |
Output is correct |
| 2 |
Correct |
21 ms |
18644 KB |
Output is correct |
| 3 |
Correct |
19 ms |
18516 KB |
Output is correct |
| 4 |
Incorrect |
22 ms |
18524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
