Submission #1036015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036015		May27_th	Triple Jump (JOI19_jumps)	C++17	0 / 100	44 ms	38124 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
int N; i64 a[500005], sparse[500005][22];
i64 getMax(int L, int R) {
  int j = log2(R - L + 1);
  return max(sparse[L][j], sparse[R - (1 << j) + 1][j]);
}
// struct Tree{
//   int n;
//   vector<int64_t>lazy;
//   vector<int64_t>st;
//   Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
//   void push(int id){
//     int64_t add = lazy[id];
//     lazy[id * 2] += add, st[id * 2] += add;
//     lazy[id * 2 + 1] += add, st[id * 2 + 1] += add;
//     lazy[id] = 0;
//   }
//   void update(int id, int l, int r, int u, int v, int64_t val){
//     if (v < l || u > r) return;
//     if (u <= l && r <= v) {
//       st[id] = val;
//       lazy[id] = val;
//       return;
//     }
//     // push(id);
//     int mid = (l + r)/2;
//     update(id * 2, l, mid, u, v, val);
//     update(id * 2 + 1, mid + 1, r, u, v, val);
//     st[id] = max(st[id * 2], st[id * 2 + 1]);
//   }
//   int find(int id, int l, int r, int u, int v, int x){
//     if (v < l || u > r) return N + 1;
//     if (st[id] <= x) return N + 1;
//     if (l == r) return l;
//     // push(id);
//     int mid = (l + r)/2;
//     int lf = find(id * 2, l, mid, u, v, x);
//     if (lf != N + 1) return lf;
//     return find(id * 2 + 1, mid + 1, r, u, v, x);
//   }
//   int get(int id, int l, int r, int u, int v) {
//     if (v < l || u > r) return 0;
//     if (u <= l && r <= v) return st[id];
//     int mid = (l + r)/2;
//     return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
//   }
// };
int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  for (int i = 1; i <= N; i ++) cin >> a[i];
  for (int i = N; i >= 1; i --) {
    sparse[i][0] = a[i];
    for (int j = 1; j <= 20; j ++) {
      if (i + (1 << (j - 1)) <= N) { 
        sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int Q; cin >> Q; while (Q --) {
    int L, R; cin >> L >> R;
    set<pair<i64, int>> s;
    for (int i = L; i <= R; i ++) {
      s.insert(mp(a[i], i));
      if (s.size() > 3) s.erase(s.begin());
    }
    vector<int> ids;
    for (auto [x, id] : s) {
      ids.pb(id);
      // cout << x << " " << id << "\n";
    }
    sort(all(ids));
    i64 ans = 0;
    for (int i = 0; i < 2; i ++) {
      for (int j = i + 1; j < 3; j ++) {
        int lf = ids[i], rg = ids[j];
        int gap = rg - lf;
        if (lf > L) {
          ans = max(ans, getMax(max(lf - gap, L), lf - 1) + a[lf] + a[rg]);
          // cout << lf << " " << rg << " " << getMax(lf - gap, lf - 1) + a[lf] + a[rg] << "\n";
        } if (rg + gap <= R) {
          ans = max(ans, a[lf] + a[rg] + getMax(rg + gap, R));
          // cout << lf << " " << rg << " " << a[lf] + a[rg] + getMax(rg + gap, R) << "\n";
        } if (gap > 1) {
          ans = max(ans, a[lf] + getMax(lf + 1, (lf + rg)/2) + a[rg]);
        }
      }
    }
    cout << ans << "\n";
  }
}

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