Submission #225385

#	Time	Username	Problem	Language	Result	Execution time	Memory
225385		Bruteforceman	Triple Jump (JOI19_jumps)	C++11	100 / 100	2961 ms	102228 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int a[maxn];
vector <int> qr[maxn];
vector <pair <int, int>> v[maxn];
int res[maxn], opt[maxn];
int l[maxn], r[maxn];
int n;

struct node {
  int mxpair, maxv, opt;
  node () {}
  node (int mxpair, int maxv, int opt) : mxpair(mxpair), maxv(maxv), opt(opt) {}
};
node operator + (node p, node q) {
  node ans;
  ans.maxv = max(p.maxv, q.maxv);
  ans.mxpair = max(p.mxpair, q.mxpair);
  ans.opt = max(p.opt, q.opt);
  ans.opt = max(ans.opt, p.mxpair + q.maxv);
  return ans;
}
node t[maxn * 4];
void build(int c = 1, int b = 1, int e = n) {
  if(b == e) {
    t[c].mxpair = 0;
    t[c].opt = t[c].maxv = a[b];
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  build(l, b, m);
  build(r, m + 1, e);
  t[c] = t[l] + t[r];
}
void update(int x, int val, int c = 1, int b = 1, int e = n) {
  if(b == e) {
    t[c].mxpair = max(t[c].mxpair, val);
    t[c].opt = t[c].mxpair + t[c].maxv;
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) update(x, val, l, b, m);
  else update(x, val, r, m + 1, e);
  t[c] = t[l] + t[r];
}
node query(int x, int y, int c = 1, int b = 1, int e = n) {
  if(x <= b && e <= y) {
    return t[c];
  }
  if(y < b || e < x) return node( 0, 0, 0);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return query(x, y, l, b, m) + query(x, y, r, m + 1, e);
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int q;
  cin >> q;
  for(int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    qr[l[i]].emplace_back(i);
  }
  stack <int> s;
  vector <pair <int, int>> imp;
  for(int i = 1; i <= n; i++) {
    while(!s.empty() && a[s.top()] <= a[i]) {
      imp.emplace_back(s.top(), i);
      s.pop();
    }
    if(!s.empty()) imp.emplace_back(s.top(), i);
    s.push(i);
  }
  for(auto i : imp) {
    if(2 * i.second - i.first <= n) {
      v[i.first].emplace_back(2 * i.second - i.first, 
          a[i.first] + a[i.second]);
    }
  }
  build();
  for(int i = n; i >= 1; i--) {
    for(auto j : v[i]) {
      if(j.first <= n) {
        update(j.first, j.second);
      }
    }
    for(auto j : qr[i]) {
      res[j] = query(l[j], r[j]).opt;
    }
  }
  for(int i = 1; i <= q; i++) {
    cout << res[i] << endl;
  }
  return 0;
}

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