Submission #165360

#	Time	Username	Problem	Language	Result	Execution time	Memory
165360		Bojack	Triple Jump (JOI19_jumps)	C++14	100 / 100	1648 ms	126540 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e14;

const int N = 5e5 + 5;

struct node {
  ll A, B, BA;
  node(ll _A = -INF, ll _B = -INF, ll _BA = -INF) {
    A = _A, B = _B, BA = _BA;
  }
};

node tree[4 * N];
int n, q;
ll a[N];
vector <int> r[N];
vector <pair <int, int>> Q[N];

node merge(node x, node y) {
  return node(max(x.A, y.A), max(x.B, y.B), max({x.BA, y.BA, x.B + y.A}));
}

void update(int node, int s, int e, int idx, ll val, bool flag) {
  if(idx < s or idx > e) return;
  if(s == e) {
    if(flag) tree[node].B = max(tree[node].B, val);
    else tree[node].A = max(tree[node].A, val);
    tree[node].BA = max(-INF, tree[node].A + tree[node].B);
    return;
  }
  int mid = (s + e) / 2;
  update(2 * node, s, mid, idx, val, flag);
  update(2 * node + 1, mid + 1, e, idx, val, flag);
  tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}

node query(int node, int s, int e, int l, int r) {
  if(l > e or r < s) return {-INF, -INF, -INF};
  if(s >= l and e <= r) {
    return tree[node];
  }
  int mid = (s + e) / 2;
  return merge(query(2 * node, s, mid, l, r), query(2 * node + 1, mid + 1, e, l, r));
}

int main() {
  scanf("%d", &n);
  stack <ll> s;
  for(int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    while(!s.empty() and a[s.top()] <= a[i]) {
      r[s.top()].push_back(i);
      s.pop();
    }
    if(!s.empty()) {
      r[s.top()].push_back(i);
    }
    s.push(i);
    update(1, 1, n, i, a[i], 0);
  }
  scanf("%d", &q);
  for(int i = 0; i < q; i++) {
    int l, r; scanf("%d %d", &l, &r);
    Q[l].push_back({r, i});
  }
  vector <ll> ans(q);
  for(int i = n; i >= 1; i--) {
    for(auto p : r[i]) {
      if(p + p - i <= n) {
        update(1, 1, n, p + p - i, a[p] + a[i], 1);
      }
    }
    for(auto p : Q[i]) {
      ans[p.second] = query(1, 1, n, i, p.first).BA;
    }
  }
  for(int i = 0; i < q; i++) {
    printf("%lld\n", ans[i]);
  }
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
jumps.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &a[i]);
     ~~~~~^~~~~~~~~~~~~~~
jumps.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
jumps.cpp:68:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int l, r; scanf("%d %d", &l, &r);
               ~~~~~^~~~~~~~~~~~~~~~~

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