oj.uz

Submission #1085333

# Submission time Handle Problem Language Result Execution time Memory
1085333 2024-09-08T03:20:30 Z rxlfd314 Triple Jump (JOI19_jumps) C++17
100 / 100
 471 ms 87376 KB 
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 500005;
int N, Q, A[mxN];
vt<ari2> queries[mxN];
vt<int> bs[mxN];

struct ST {
  struct Node {
    int ans, c, ab;
    Node operator+(const Node &other) {
      return {
        max({ans, other.ans, ab + other.c}), 
        max(c, other.c),
        max(ab, other.ab)
      };
    }
  } st[mxN<<1];
  void build() {
    FOR(i, 0, N-1)
      st[i+N] = {0, A[i], 0};
    ROF(i, N-1, 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  void update(int i, int v) {
    i += N;
    st[i].ab = max(st[i].ab, v);
    st[i].ans = st[i].ab + st[i].c;
    for (i >>= 1; i > 0; i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node lft = {0, 0, 0}, rht = {0, 0, 0};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        lft = lft + st[l++];
      if (r & 1)
        rht = st[--r] + rht;
    }
    return lft + rht;
  }
} st;

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N;
  FOR(i, 0, N-1)
    cin >> A[i];
  
  cin >> Q;
  FOR(i, 0, Q-1) {
    int l, r; cin >> l >> r, l--, r--;
    queries[l].push_back({r, i});
  }
  
  vt<int> sk;
  FOR(i, 0, N-1) {
    while (size(sk) && A[sk.back()] <= A[i]) {
      bs[sk.back()].push_back(i);
      sk.pop_back();
    }
    if (size(sk))
      bs[sk.back()].push_back(i);
    sk.push_back(i);
  }
  
  st.build();
  vt<int> ans(Q);
  ROF(i, N-3, 0) {
    for (int j : bs[i]) {
      if (2 * j - i >= N)
        continue;
      st.update(2 * j - i, A[i] + A[j]);
    }
    for (auto [r, qi] : queries[i])
      ans[qi] = st.query(i, r).ans;
  }
  
  for (auto &i : ans)
    cout << i << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23848 KB Output is correct
6 Correct 12 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23848 KB Output is correct
6 Correct 12 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 138 ms 42568 KB Output is correct
12 Correct 132 ms 42576 KB Output is correct
13 Correct 124 ms 42632 KB Output is correct
14 Correct 139 ms 42592 KB Output is correct
15 Correct 137 ms 42660 KB Output is correct
16 Correct 134 ms 42064 KB Output is correct
17 Correct 134 ms 41808 KB Output is correct
18 Correct 142 ms 41816 KB Output is correct
19 Correct 137 ms 42404 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 37436 KB Output is correct
2 Correct 50 ms 37200 KB Output is correct
3 Correct 62 ms 37964 KB Output is correct
4 Correct 79 ms 37456 KB Output is correct
5 Correct 85 ms 37460 KB Output is correct
6 Correct 81 ms 36988 KB Output is correct
7 Correct 79 ms 36944 KB Output is correct
8 Correct 78 ms 36668 KB Output is correct
9 Correct 78 ms 37212 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23848 KB Output is correct
6 Correct 12 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 138 ms 42568 KB Output is correct
12 Correct 132 ms 42576 KB Output is correct
13 Correct 124 ms 42632 KB Output is correct
14 Correct 139 ms 42592 KB Output is correct
15 Correct 137 ms 42660 KB Output is correct
16 Correct 134 ms 42064 KB Output is correct
17 Correct 134 ms 41808 KB Output is correct
18 Correct 142 ms 41816 KB Output is correct
19 Correct 137 ms 42404 KB Output is correct
20 Correct 86 ms 37436 KB Output is correct
21 Correct 50 ms 37200 KB Output is correct
22 Correct 62 ms 37964 KB Output is correct
23 Correct 79 ms 37456 KB Output is correct
24 Correct 85 ms 37460 KB Output is correct
25 Correct 81 ms 36988 KB Output is correct
26 Correct 79 ms 36944 KB Output is correct
27 Correct 78 ms 36668 KB Output is correct
28 Correct 78 ms 37212 KB Output is correct
29 Correct 464 ms 81680 KB Output is correct
30 Correct 336 ms 80892 KB Output is correct
31 Correct 371 ms 82984 KB Output is correct
32 Correct 461 ms 81488 KB Output is correct
33 Correct 471 ms 81584 KB Output is correct
34 Correct 457 ms 79184 KB Output is correct
35 Correct 467 ms 78932 KB Output is correct
36 Correct 450 ms 78932 KB Output is correct
37 Correct 447 ms 80464 KB Output is correct
38 Correct 329 ms 87260 KB Output is correct
39 Correct 337 ms 87376 KB Output is correct
40 Correct 328 ms 84052 KB Output is correct
41 Correct 323 ms 83536 KB Output is correct
42 Correct 319 ms 83344 KB Output is correct
43 Correct 329 ms 85156 KB Output is correct
44 Correct 356 ms 86612 KB Output is correct
45 Correct 359 ms 86584 KB Output is correct
46 Correct 348 ms 83536 KB Output is correct
47 Correct 335 ms 83028 KB Output is correct
48 Correct 330 ms 83284 KB Output is correct
49 Correct 335 ms 85072 KB Output is correct
50 Correct 410 ms 84560 KB Output is correct
51 Correct 364 ms 84488 KB Output is correct
52 Correct 368 ms 82000 KB Output is correct
53 Correct 368 ms 81868 KB Output is correct
54 Correct 385 ms 81744 KB Output is correct
55 Correct 382 ms 83536 KB Output is correct