oj.uz

답안 #783091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783091 2023-07-14T15:17:32 Z tvladm2009 3단 점프 (JOI19_jumps) C++17
27 / 100
 136 ms 60688 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = (int) 5e5 + 7;
const int INF = (int) 2e9;
int n, a[N], nextBigger[N], q;

struct rmq {
  const int K = 20;
  vector<vector<int>> tab;
  vector<int> lg2;
  int n;

  void init(int nn) {
    n = nn;
    lg2.resize(n + 1);
    for (int i = 2; i <= n; i++) {
      lg2[i] = 1 + lg2[i / 2];
    }
    tab.resize(K);
    for (int i = 0; i < K; i++) {
      tab[i].resize(n + 1);
    }
  }

  void build(int a[]) {
    for (int i = 1; i <= n; i++) {
      tab[0][i] = a[i];
    }
    for (int k = 1; k < K; k++) {
      for (int i = 1; i + (1 << k) - 1 <= n; i++) {
        tab[k][i] = max(tab[k - 1][i], tab[k - 1][i + (1 << (k - 1))]);
      }
    }
  }

  int query(int x, int y) {
    if (x > y) {
      return -INF;
    }
    assert(1 <= x && x <= y && y <= n);
    int p = lg2[y - x + 1];
    return max(tab[p][x], tab[p][y - (1 << p) + 1]);
  }
};

struct Offer {
  int value;
  int lft;
  int rgh;
};

struct Question {
  int l;
  int r;
  int ind;
};

bool operator < (Offer a, Offer b) {
  return a.lft > b.lft;
}

vector<Question> questionsAt[N];
int best[N];

struct node {
  int maxA;
  int maxAB;
};

node operator + (node a, node b) {
  return {max(a.maxA, b.maxA), max(a.maxAB, b.maxAB)};
}

node t[4 * N];
int applyToAll[4 * N];

void push(int v, int tl, int tr) {
  if (applyToAll[v] == -INF) {
    return;
  }
  if (tl < tr) {
    applyToAll[2 * v] = max(applyToAll[2 * v], applyToAll[v]);
    applyToAll[2 * v + 1] = max(applyToAll[2 * v + 1], applyToAll[v]);
  }
  t[v].maxAB = max(t[v].maxAB, t[v].maxA + applyToAll[v]);
  applyToAll[v] = -INF;
}

void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].maxA = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = t[2 * v] + t[2 * v + 1];
  }
}

void apply(int v, int tl, int tr, int l, int r, int x) {
  push(v, tl, tr);
  if (l <= tl && tr <= r) {
    applyToAll[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (l <= tm) {
    apply(2 * v, tl, tm, l, min(tm, r), x);
  }
  if (tm + 1 <= r) {
    apply(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
  }
  t[v] = t[2 * v] + t[2 * v + 1];
}

node get(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  if (l <= tm && r <= tm) {
    return get(2 * v, tl, tm, l, r);
  } else if (tm + 1 <= l && tm + 1 <= r) {
    return get(2 * v + 1, tm + 1, r, l, r);
  } else {
    return get(2 * v, tl, tm, l, tm) + get(2 * v + 1, tm + 1, tr, tm + 1, r);
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  //freopen("input", "r", stdin);

  for (int i = 0; i < 4 * N; i++) {
    applyToAll[i] = -INF;
    t[i].maxA = -INF;
    t[i].maxAB = -INF;
  }

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, 1, n);
  rmq rmq;
  rmq.init(n);
  rmq.build(a);

  {
    vector<int> st;
    for (int i = n; i >= 1; i--) {
      while (!st.empty() && a[i] >= a[st.back()]) {
        st.pop_back();
      }
      if (st.empty()) {
        nextBigger[i] = n + 1;
      } else {
        nextBigger[i] = st.back();
      }
      st.push_back(i);
    }
  }

  vector<Offer> offers;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= min(n, nextBigger[i]); j = nextBigger[j]) {
      if (2 * j - i <= n) {
        offers.push_back({a[i] + a[j], i, 2 * j - i});
      }
    }
  }
  sort(offers.begin(), offers.end());

  cin >> q;
  vector<int> sol(q, -1);
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    questionsAt[l].push_back({l, r, i});
  }

  for (int i = 1; i <= n; i++) {
    best[i] = -INF;
  }

  int last = -1;

  for (int l = n; l >= 1; l--) {
    while (last + 1 < (int) offers.size() && l <= offers[last + 1].lft) {
      last++;
      apply(1, 1, n, offers[last].rgh, n, offers[last].value);
    }
    for (auto &it : questionsAt[l]) {
      sol[it.ind] = get(1, 1, n, l, it.r).maxAB;
    }
  }
  for (auto &x : sol) {
    assert(x != -1);
    cout << x << "\n";
  }
  return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB Output is correct
2 Incorrect 15 ms 35564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB Output is correct
2 Incorrect 15 ms 35564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 60604 KB Output is correct
2 Correct 83 ms 59056 KB Output is correct
3 Correct 90 ms 57668 KB Output is correct
4 Correct 136 ms 60572 KB Output is correct
5 Correct 135 ms 60580 KB Output is correct
6 Correct 131 ms 60632 KB Output is correct
7 Correct 134 ms 60620 KB Output is correct
8 Correct 132 ms 60688 KB Output is correct
9 Correct 133 ms 60648 KB Output is correct

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB Output is correct
2 Incorrect 15 ms 35564 KB Output isn't correct
3 Halted 0 ms 0 KB -