oj.uz

Submission #872992

# Submission time Handle Problem Language Result Execution time Memory
872992 2023-11-14T08:54:45 Z NeroZein Triple Jump (JOI19_jumps) C++17
100 / 100
 769 ms 89680 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 5e5 + 5;

struct node {
  int ans;
  int ab, c;
};

node seg[N * 2]; 

node merge(const node& lx, const node& rx) {
  node ret;
  ret.ans = max(lx.ans, rx.ans); 
  if (lx.ab) {
    ret.ans = max(ret.ans, lx.ab + rx.c); 
  }
  ret.ab = max(lx.ab, rx.ab);
  ret.c = max(lx.c, rx.c); 
  return ret;
}

void build(int nd, int l, int r, const vector<int>& c) {
  if (l == r) {
    seg[nd].c = c[l];
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid, c);
  build(rs, mid + 1, r, c);
  seg[nd].c = max(seg[nd + 1].c, seg[rs].c); 
}

void upd(int nd, int l, int r, int p, int v) {
  if (l == r) {
    seg[nd].ab = max(seg[nd].ab, v);
    seg[nd].ans = max(seg[nd].ans, seg[nd].ab + seg[nd].c); 
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = merge(seg[nd + 1], seg[rs]); 
}

node qry(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd]; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  node ret;
  if (mid >= e) {
    ret = qry(nd + 1, l, mid, s, e);
  } else {
    if (mid < s) {
      ret = qry(rs, mid + 1, r, s, e); 
    } else {
      ret = merge(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i]; 
  }
  build(0, 0, n - 1, a); 
  vector<vector<pair<int, int>>> vec(n); 
  stack<int> stk; 
  for (int i = 0; i < n; ++i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      if (2 * i - stk.top() < n) {
        vec[stk.top()].emplace_back(2 * i - stk.top(), a[i] + a[stk.top()]);
      }
      stk.pop(); 
    }
    if (!stk.empty()) {
      if (2 * i - stk.top() < n) {
        vec[stk.top()].emplace_back(2 * i - stk.top(), a[i] + a[stk.top()]);
      }
    }
    stk.push(i); 
  }
  int q;
  cin >> q; 
  vector<int> ans(q); 
  vector<vector<pair<int, int>>> qs(n); 
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    qs[l].emplace_back(r, i); 
  }
  for (int l = n - 1; l >= 0; --l) {
    for (auto [p, s] : vec[l]) {
      upd(0, 0, n - 1, p, s); 
    }
    for (auto [r, i] : qs[l]) {
      ans[i] = qry(0, 0, n - 1, 0, r).ans; 
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n'; 
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 173 ms 19500 KB Output is correct
12 Correct 171 ms 19360 KB Output is correct
13 Correct 162 ms 19412 KB Output is correct
14 Correct 174 ms 19728 KB Output is correct
15 Correct 165 ms 19432 KB Output is correct
16 Correct 174 ms 19012 KB Output is correct
17 Correct 161 ms 18772 KB Output is correct
18 Correct 165 ms 18768 KB Output is correct
19 Correct 162 ms 19412 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 24440 KB Output is correct
2 Correct 73 ms 23220 KB Output is correct
3 Correct 72 ms 23900 KB Output is correct
4 Correct 127 ms 24448 KB Output is correct
5 Correct 127 ms 24400 KB Output is correct
6 Correct 124 ms 24452 KB Output is correct
7 Correct 129 ms 24440 KB Output is correct
8 Correct 126 ms 24408 KB Output is correct
9 Correct 124 ms 24400 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 173 ms 19500 KB Output is correct
12 Correct 171 ms 19360 KB Output is correct
13 Correct 162 ms 19412 KB Output is correct
14 Correct 174 ms 19728 KB Output is correct
15 Correct 165 ms 19432 KB Output is correct
16 Correct 174 ms 19012 KB Output is correct
17 Correct 161 ms 18772 KB Output is correct
18 Correct 165 ms 18768 KB Output is correct
19 Correct 162 ms 19412 KB Output is correct
20 Correct 128 ms 24440 KB Output is correct
21 Correct 73 ms 23220 KB Output is correct
22 Correct 72 ms 23900 KB Output is correct
23 Correct 127 ms 24448 KB Output is correct
24 Correct 127 ms 24400 KB Output is correct
25 Correct 124 ms 24452 KB Output is correct
26 Correct 129 ms 24440 KB Output is correct
27 Correct 126 ms 24408 KB Output is correct
28 Correct 124 ms 24400 KB Output is correct
29 Correct 724 ms 84076 KB Output is correct
30 Correct 518 ms 81020 KB Output is correct
31 Correct 564 ms 83332 KB Output is correct
32 Correct 680 ms 84048 KB Output is correct
33 Correct 670 ms 84200 KB Output is correct
34 Correct 661 ms 82040 KB Output is correct
35 Correct 769 ms 81660 KB Output is correct
36 Correct 670 ms 81488 KB Output is correct
37 Correct 721 ms 83176 KB Output is correct
38 Correct 526 ms 89680 KB Output is correct
39 Correct 532 ms 89488 KB Output is correct
40 Correct 519 ms 86568 KB Output is correct
41 Correct 517 ms 86000 KB Output is correct
42 Correct 520 ms 86104 KB Output is correct
43 Correct 568 ms 87820 KB Output is correct
44 Correct 546 ms 89124 KB Output is correct
45 Correct 533 ms 89316 KB Output is correct
46 Correct 535 ms 86148 KB Output is correct
47 Correct 527 ms 85708 KB Output is correct
48 Correct 527 ms 85588 KB Output is correct
49 Correct 527 ms 87632 KB Output is correct
50 Correct 596 ms 87440 KB Output is correct
51 Correct 596 ms 87280 KB Output is correct
52 Correct 580 ms 85104 KB Output is correct
53 Correct 567 ms 84816 KB Output is correct
54 Correct 553 ms 84612 KB Output is correct
55 Correct 595 ms 86240 KB Output is correct