oj.uz

Submission #199497

# Submission time Handle Problem Language Result Execution time Memory
199497 2020-02-01T16:10:30 Z houtaru Triple Jump (JOI19_jumps) C++17
100 / 100
 856 ms 78200 KB 
#include <bits/stdc++.h>

using namespace std;

typedef array<int, 3> Node; // 0/1/2: c/ab/abc

const int maxn = 1 << 19;
const int INF = 1e9;

int n, q;
int A[maxn];
vector<int> p[maxn];
vector<pair<int, int>> query[maxn];

struct segtree {
  Node T[maxn << 1];

  Node upd(const Node&x, const Node& y) {
    return {max(x[0], y[0]), max(x[1], y[1]), max({x[1] + y[0], x[2], y[2]})};
  }
  
  void init() {
    for (int i = maxn; i < maxn << 1; ++i) T[i] = {A[i - maxn], -INF, -INF};
    for (int i = maxn - 1; i > 0; --i) T[i] = upd(T[2 * i], T[2 * i + 1]);
  }

  void update(int i, int v) {
    i += maxn;
    T[i][1] = max(T[i][1], v);
    T[i][2] = max(T[i][2], T[i][1]  + T[i][0]);
    for (i >>= 1; i > 0; i >>= 1) {
      T[i] = upd(T[2 * i], T[2 * i + 1]);
    }
  }

  int get(int l, int r) {
    Node L = {-INF, -INF, -INF};
    Node R = L;
    for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        L = upd(L, T[l]);
        l++;
      }
      if (r & 1) {
        r--;
        R = upd(T[r], R);
      }
    }
    return upd(L, R)[2];
  }
} seg;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  cin >> n;
  
  stack<int> st;
  for (int i = 0; i < n; ++i) {
    cin >> A[i];

    while (!st.empty()) {
      int j = st.top(), k = 2 * i - j;
      if (k < n) p[j].push_back(k);
      if (A[j] <= A[i]) st.pop();
      else break;
    }
    st.push(i);
  }    
  seg.init();
  
  cin >> q;
  vector<int> answer(q, 0);
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r;
    query[l - 1].emplace_back(r - 1, i);
  }

  for (int i = n - 1; i >= 0; --i) {
    for (int j : p[i]) {
      seg.update(j, A[i] + A[(i + j) / 2]);    }
    for (auto it : query[i]) {
      answer[it.second] = seg.get(i, it.first + 1);
    }
  }
  for (int i = 0; i < q; ++i) cout << answer[i] << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37240 KB Output is correct
2 Correct 28 ms 37240 KB Output is correct
3 Correct 27 ms 37112 KB Output is correct
4 Correct 28 ms 37240 KB Output is correct
5 Correct 28 ms 37240 KB Output is correct
6 Correct 26 ms 37244 KB Output is correct
7 Correct 27 ms 37240 KB Output is correct
8 Correct 26 ms 37240 KB Output is correct
9 Correct 28 ms 37240 KB Output is correct
10 Correct 29 ms 37240 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37240 KB Output is correct
2 Correct 28 ms 37240 KB Output is correct
3 Correct 27 ms 37112 KB Output is correct
4 Correct 28 ms 37240 KB Output is correct
5 Correct 28 ms 37240 KB Output is correct
6 Correct 26 ms 37244 KB Output is correct
7 Correct 27 ms 37240 KB Output is correct
8 Correct 26 ms 37240 KB Output is correct
9 Correct 28 ms 37240 KB Output is correct
10 Correct 29 ms 37240 KB Output is correct
11 Correct 244 ms 50808 KB Output is correct
12 Correct 231 ms 50808 KB Output is correct
13 Correct 233 ms 50936 KB Output is correct
14 Correct 239 ms 50936 KB Output is correct
15 Correct 252 ms 50808 KB Output is correct
16 Correct 224 ms 50168 KB Output is correct
17 Correct 252 ms 50168 KB Output is correct
18 Correct 224 ms 50196 KB Output is correct
19 Correct 226 ms 50680 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 44536 KB Output is correct
2 Correct 97 ms 44408 KB Output is correct
3 Correct 91 ms 45180 KB Output is correct
4 Correct 127 ms 44536 KB Output is correct
5 Correct 129 ms 44536 KB Output is correct
6 Correct 144 ms 44536 KB Output is correct
7 Correct 118 ms 44536 KB Output is correct
8 Correct 122 ms 44536 KB Output is correct
9 Correct 125 ms 44664 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37240 KB Output is correct
2 Correct 28 ms 37240 KB Output is correct
3 Correct 27 ms 37112 KB Output is correct
4 Correct 28 ms 37240 KB Output is correct
5 Correct 28 ms 37240 KB Output is correct
6 Correct 26 ms 37244 KB Output is correct
7 Correct 27 ms 37240 KB Output is correct
8 Correct 26 ms 37240 KB Output is correct
9 Correct 28 ms 37240 KB Output is correct
10 Correct 29 ms 37240 KB Output is correct
11 Correct 244 ms 50808 KB Output is correct
12 Correct 231 ms 50808 KB Output is correct
13 Correct 233 ms 50936 KB Output is correct
14 Correct 239 ms 50936 KB Output is correct
15 Correct 252 ms 50808 KB Output is correct
16 Correct 224 ms 50168 KB Output is correct
17 Correct 252 ms 50168 KB Output is correct
18 Correct 224 ms 50196 KB Output is correct
19 Correct 226 ms 50680 KB Output is correct
20 Correct 129 ms 44536 KB Output is correct
21 Correct 97 ms 44408 KB Output is correct
22 Correct 91 ms 45180 KB Output is correct
23 Correct 127 ms 44536 KB Output is correct
24 Correct 129 ms 44536 KB Output is correct
25 Correct 144 ms 44536 KB Output is correct
26 Correct 118 ms 44536 KB Output is correct
27 Correct 122 ms 44536 KB Output is correct
28 Correct 125 ms 44664 KB Output is correct
29 Correct 856 ms 72444 KB Output is correct
30 Correct 694 ms 71696 KB Output is correct
31 Correct 684 ms 73848 KB Output is correct
32 Correct 805 ms 72440 KB Output is correct
33 Correct 812 ms 72472 KB Output is correct
34 Correct 760 ms 71744 KB Output is correct
35 Correct 791 ms 71612 KB Output is correct
36 Correct 774 ms 71672 KB Output is correct
37 Correct 797 ms 72184 KB Output is correct
38 Correct 503 ms 78040 KB Output is correct
39 Correct 501 ms 78200 KB Output is correct
40 Correct 497 ms 76408 KB Output is correct
41 Correct 494 ms 76128 KB Output is correct
42 Correct 482 ms 76152 KB Output is correct
43 Correct 505 ms 77048 KB Output is correct
44 Correct 540 ms 77432 KB Output is correct
45 Correct 529 ms 77428 KB Output is correct
46 Correct 504 ms 76024 KB Output is correct
47 Correct 510 ms 75768 KB Output is correct
48 Correct 505 ms 75768 KB Output is correct
49 Correct 533 ms 77048 KB Output is correct
50 Correct 596 ms 75768 KB Output is correct
51 Correct 593 ms 75624 KB Output is correct
52 Correct 578 ms 74752 KB Output is correct
53 Correct 581 ms 74872 KB Output is correct
54 Correct 577 ms 74744 KB Output is correct
55 Correct 577 ms 75512 KB Output is correct