제출 #441489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441489		peijar	3단 점프 (JOI19_jumps)	C++17	32 / 100	4072 ms	20164 KiB

jumps

#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 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54