Submission #783094

#	Time	Username	Problem	Language	Result	Execution time	Memory
783094		tvladm2009	Triple Jump (JOI19_jumps)	C++17	100 / 100	882 ms	127944 KiB

jumps

#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;
  }
  t[v].maxAB = max(t[v].maxAB, t[v].maxA + applyToAll[v]);
  if (tl < tr) {
    applyToAll[2 * v] = max(applyToAll[2 * v], applyToAll[v]);
    applyToAll[2 * v + 1] = max(applyToAll[2 * v + 1], 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 (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    applyToAll[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  apply(2 * v, tl, tm, l, r, x);
  apply(2 * v + 1, tm + 1, tr, l, 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 (tr < l || r < tl) {
    return {-INF, -INF};
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, 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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54