Submission #295408

# Submission time Handle Problem Language Result Execution time Memory
295408 2020-09-09T16:27:27 Z erd1 Triple Jump (JOI19_jumps) C++14
0 / 100
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 -