#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)
out << (i == b?"":" ") << *i;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
return outIt(out << '[', all(v)) << ']';
}
struct node;
vector<node*> nodes;
vector<int> v, tmp;
struct node{
node *L, *R;
int l, r, cnt, val = 0;
node(int ll, int rr, int c = 0): l{ll}, r{rr}, cnt{c} {
if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
}
node(node* n, int v){
l = n->l, r = n->r, cnt = n->cnt+1, L = n->L, R = n->R, val = v;
}
node* update(int x, int v){
node* ret = new node(this, v);
if(l == r) return ret;
else if(x <= (l+r>>1))
ret->L = ret->L->update(x, v);
else
ret->R = ret->R->update(x, v);
return ret;
}
friend int query(node* a, node* b, int k){
if(a->l == a->r)return b->val-1;
if(b->R->cnt - a->R->cnt > k)
return query(a->R, b->R, k);
else
return query(a->L, b->L, k - (b->R->cnt - a->R->cnt));
}
};
int qmax(int a, int b){
//cout << a << " " << b << endl;
if(a > b)return -2e8;
int ans = query(nodes[a], nodes[b+1], 0);
//cout << a << " " << b << " " << ans << endl;
//assert(a < ans+1 && ans <= b);
return v[ans];
}
//array<array<int, 5000>, 5000> ans;
vector<pii> v2;
signed main(){ ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++){
int a; cin >> a;
v.pb(a);
v2.pb({a, -i});
}
sort(all(v2));
nodes.pb(new node(0, v2.size()-1));
for(int i = 0; i < n; i++)
nodes.pb(nodes.back()->update(lower_bound(all(v2), make_pair(v[i], -i))-v2.begin(), i+1));
/*
for(int i = 0; i < n; i++)
for(int j = i+2, mx = -1; j < n; j++) {
if((i+j)%2 == 0) mx = max(mx, v[i+j>>1]);
ans[i][j] = v[i]+v[j]+mx;
}
for(int l = 3; l < n; l++)
for(int i = 0, j = l; j < n; i++, j++)
ans[i][j] = max({ans[i][j], ans[i+1][j], ans[i][j-1]});
*/
int q;
cin >> q;
while(q--){
int a, b; cin >> a >> b;
tmp.resize(0);
for(int i = 0; i < b-a+1; i++){
int nxt = query(nodes[a-1], nodes[b], i);
tmp.pb(nxt);
if(tmp.size() < __lg(b-a+1) && tmp.size() != b-a+1) continue;
/*
sort(all(tmp)), reverse(all(tmp));
if(tmp[i-1]-tmp[i] > tmp[0]-tmp[i-1])
continue;
*/
sort(all(tmp));
int anss = 0;
//cout << tmp << endl;
for(int j = 0; j < tmp.size(); j++)
for(int k = a-1; k < b; k++){
int x = tmp[j], y = k;
if(x == y)continue;
if(x > y)swap(x, y);
anss = max(anss, v[x]+v[y]+max({qmax(max(a-1, x-(y-x)), x-1), qmax(x+1, (x+y)/2), qmax(y+(y-x), b-1)}));
}
/*
for(int j = 0; j < tmp.size()-2; j++)
for(int k = j+1; k < tmp.size()-1; k++){
int x = tmp[j], y = tmp[k];
if(v[x]+v[y]+qmax(max(a-1, x-(y-x)), x-1) == anss)
cout << x << " l " << y << endl;
if(v[x]+v[y]+qmax(x+1, (x+y)/2) == anss)
cout << x << " m " << y << endl;
if(v[x]+v[y]+qmax(y+(y-x), b-1) == anss)
cout << x << " r " << y << endl;
//anss = max(anss, v[x]+v[y]+max({qmax(max(a, x-(y-x)), x-1), qmax(x+1, (x+y)/2), qmax(y+(y-x), b)}));
}*/
if(anss != 0) {
cout << anss << endl;
break;
}
}
//cout << ans[a-1][b-1] << endl;
}
}
Compilation message
jumps.cpp: In constructor 'node::node(int, int, int)':
jumps.cpp:30:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
| ~^~
jumps.cpp:30:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
| ~^~
jumps.cpp: In member function 'node* node::update(int, int)':
jumps.cpp:38:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | else if(x <= (l+r>>1))
| ~^~
jumps.cpp: In function 'int main()':
jumps.cpp:95:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | if(tmp.size() < __lg(b-a+1) && tmp.size() != b-a+1) continue;
| ~~~~~~~~~~~^~~~~~~~~~~~~
jumps.cpp:95:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | if(tmp.size() < __lg(b-a+1) && tmp.size() != b-a+1) continue;
| ~~~~~~~~~~~^~~~~~~~
jumps.cpp:104:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = 0; j < tmp.size(); j++)
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
4064 ms |
4132 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1713 ms |
198632 KB |
Output is correct |
| 2 |
Correct |
1167 ms |
198772 KB |
Output is correct |
| 3 |
Correct |
1427 ms |
198748 KB |
Output is correct |
| 4 |
Correct |
1575 ms |
198748 KB |
Output is correct |
| 5 |
Correct |
1547 ms |
198880 KB |
Output is correct |
| 6 |
Correct |
1486 ms |
198600 KB |
Output is correct |
| 7 |
Correct |
1626 ms |
198752 KB |
Output is correct |
| 8 |
Correct |
1603 ms |
198748 KB |
Output is correct |
| 9 |
Correct |
1424 ms |
198752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
4064 ms |
4132 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
