제출 #441511

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

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = (1 << 20) + 1;
const int INF = -1e18;
int iDeb[MAXN], iFin[MAXN], lazyMax[MAXN], maxVal[MAXN], strengh[MAXN],
    maxStrength[MAXN];

void buildTree(int iNoeud, int deb, int fin) {
  iDeb[iNoeud] = deb, iFin[iNoeud] = fin;
  lazyMax[iNoeud] = INF;

  if (deb == fin) {
    maxStrength[iNoeud] = strengh[deb];
    maxVal[iNoeud] = INF;
    return;
  }
  buildTree(2 * iNoeud, deb, (deb + fin) / 2);
  buildTree(2 * iNoeud + 1, (deb + fin) / 2 + 1, fin);
  maxVal[iNoeud] = INF;
  maxStrength[iNoeud] =
      max(maxStrength[2 * iNoeud], maxStrength[2 * iNoeud + 1]);
}

void push(int iNoeud) {
  if (lazyMax[iNoeud] == INF)
    return;

  maxVal[iNoeud] = max(maxVal[iNoeud], maxStrength[iNoeud] + lazyMax[iNoeud]);
  if (iDeb[iNoeud] < iFin[iNoeud]) {
    lazyMax[iNoeud * 2] = max(lazyMax[2 * iNoeud], lazyMax[iNoeud]);
    lazyMax[1 + iNoeud * 2] = max(lazyMax[2 * iNoeud], lazyMax[iNoeud]);
  }
  lazyMax[iNoeud] = INF;
}

void upd(int iNoeud, int deb, int fin, int v) {
  push(iNoeud);
  if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
    return;
  if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin) {
    lazyMax[iNoeud] = v;
    push(iNoeud);
    return;
  }
  upd(2 * iNoeud, deb, fin, v);
  upd(1 + 2 * iNoeud, deb, fin, v);
  maxVal[iNoeud] = max(maxVal[2 * iNoeud], maxVal[2 * iNoeud + 1]);
}

int query(int iNoeud, int deb, int fin) {
  push(iNoeud);
  if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
    return INF;
  if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin)
    return maxVal[iNoeud];
  return max(query(2 * iNoeud, deb, fin), query(2 * iNoeud + 1, deb, fin));
}

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

  int N;
  cin >> N;
  for (int i = 0; i < N; ++i)
    cin >> 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[pos].push_back(b);
      if (val >= strengh[b])
        break;
    }
  }

  int Q;
  cin >> Q;
  vector<vector<pair<int, int>>> queries(N);
  vector<int> ret(Q);
  for (int i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    queries[l].emplace_back(r, i);
  }
  buildTree(1, 0, N - 1);
  for (int a = N - 1; a >= 0; --a) {
    for (int b : interessants[a]) {
      if (b + b - a < N)
        upd(1, 2 * b - a, N - 1, strengh[a] + strengh[b]);
    }
    for (auto [r, id] : queries[a])
      ret[id] = query(1, a + 2, r);
  }

  for (auto v : ret)
    cout << v << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54