| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 295408 |
2020-09-09T16:27:27 Z |
erd1 |
Triple Jump (JOI19_jumps) |
C++14 |
|
494 ms |
198784 KB |
#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;
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;
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));
}
};
//array<array<int, 5000>, 5000> ans;
vector<int> v, tmp;
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));
/*
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() < 3) continue;
/*
sort(all(tmp)), reverse(all(tmp));
if(tmp[i-1]-tmp[i] > tmp[0]-tmp[i-1])
continue;
*/
int anss = 0;
//cout << nxt << tmp << endl;
for(int j = 0; j < tmp.size()-2; j++)
for(int k = j+1; k < tmp.size()-1; k++){
int l = min({tmp[j], tmp[k], nxt}), r = max({tmp[j], tmp[k], nxt}), m = tmp[j] + tmp[k] + nxt - l - r;
//cout << l << " " << m << " " << r << endl;
if(m-l <= r-m)
anss = max(anss, v[l]+v[r]+v[m]);
}
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:28:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
| ~^~
jumps.cpp:28:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | 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:36:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | else if(x <= (l+r>>1))
| ~^~
jumps.cpp: In function 'int main()':
jumps.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int j = 0; j < tmp.size()-2; j++)
| ~~^~~~~~~~~~~~~~
jumps.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int k = j+1; k < tmp.size()-1; k++){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
488 ms |
198624 KB |
Output is correct |
| 2 |
Correct |
273 ms |
198588 KB |
Output is correct |
| 3 |
Correct |
297 ms |
198620 KB |
Output is correct |
| 4 |
Correct |
475 ms |
198624 KB |
Output is correct |
| 5 |
Correct |
494 ms |
198620 KB |
Output is correct |
| 6 |
Incorrect |
384 ms |
198784 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
