Submission #295479

#	Time	Username	Problem	Language	Result	Execution time	Memory
295479		erd1	Triple Jump (JOI19_jumps)	C++14	32 / 100	4064 ms	198880 KiB

jumps

#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 (stderr)

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++)
      |                      ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54