oj.uz

Submission #441489

# Submission time Handle Problem Language Result Execution time Memory
441489 2021-07-05T09:13:48 Z peijar Triple Jump (JOI19_jumps) C++17
32 / 100
 4000 ms 20164 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct rangeMax {
  vector<int> seg;
  int p, deb;

  rangeMax(int N) {
    p = 0;
    while ((1 << p) < N)
      ++p;
    seg.assign((1 << (1 + p)) + 1, 0);
    deb = (1 << p);
  }

  void update(int id, int val) {
    id += deb;
    seg[id] = val;
    while (id) {
      id = id / 2;
      seg[id] = max(seg[2 * id], seg[2 * id + 1]);
    }
  }

  int query(int l, int r) {
    int ret(0);
    l += deb;
    r += deb;
    while (l < r) {
      if (l % 2)
        ret = max(ret, seg[l]);
      if (r % 2 == 0)
        ret = max(ret, seg[r]);
      l = (l + 1) / 2;
      r = (r - 1) / 2;
    }
    if (l == r)
      ret = max(ret, seg[r]);
    return ret;
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> strengh(N);
  for (int i = 0; i < N; ++i)
    cin >> strengh[i];
  rangeMax seg(N);
  for (int i = 0; i < N; ++i)
    seg.update(i, strengh[i]);

  vector<vector<int>> interessants(N);
  vector<pair<int, int>> curRecords;
  for (int b = 1; b < N; ++b) {
    while (!curRecords.empty() and curRecords.back().first <= strengh[b - 1])
      curRecords.pop_back();
    curRecords.emplace_back(strengh[b - 1], b - 1);
    for (int i = (int)curRecords.size() - 1; i >= 0; --i) {
      auto [val, pos] = curRecords[i];
      if (b - pos + b < N)
        interessants[b].push_back(pos);
      if (val >= strengh[b])
        break;
    }
  }

  int Q;
  cin >> Q;
  for (int i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    int ret = 0;
    for (int b = l + 1; b < r; ++b)
      for (auto a : interessants[b])
        if (a >= l and 2 * b - a <= r)
          // for (int j = 2 * b - a; j <= r; ++j)
          // ret = max(ret, strengh[a] + strengh[b] + strengh[j]);
          ret = max(ret, strengh[a] + strengh[b] + seg.query(2 * b - a, r));
    cout << ret << '\n';
  }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Execution timed out 4072 ms 1440 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 18284 KB Output is correct
2 Correct 71 ms 16988 KB Output is correct
3 Correct 74 ms 20164 KB Output is correct
4 Correct 94 ms 18264 KB Output is correct
5 Correct 93 ms 18264 KB Output is correct
6 Correct 90 ms 18280 KB Output is correct
7 Correct 88 ms 18268 KB Output is correct
8 Correct 88 ms 18280 KB Output is correct
9 Correct 90 ms 18264 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Execution timed out 4072 ms 1440 KB Time limit exceeded
12 Halted 0 ms 0 KB -