Submission #295387

# Submission time Handle Problem Language Result Execution time Memory
295387 2020-09-09T16:15:42 Z erd1 Triple Jump (JOI19_jumps) C++14
0 / 100
504 ms 200544 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(auto i: tmp)
        for(auto j: tmp)
          if(i != j && i != nxt && j != nxt)
            anss = max(anss, v[i]+v[j]+v[nxt]);
      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))
      |                   ~^~
# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 504 ms 200480 KB Output is correct
2 Correct 266 ms 200544 KB Output is correct
3 Correct 277 ms 200416 KB Output is correct
4 Incorrect 479 ms 200416 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -