oj.uz

Submission #783098

# Submission time Handle Problem Language Result Execution time Memory
783098 2023-07-14T15:25:06 Z tvladm2009 Triple Jump (JOI19_jumps) C++17
100 / 100
 919 ms 127836 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;
  }
  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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 16 ms 35540 KB Output is correct
3 Correct 15 ms 35524 KB Output is correct
4 Correct 17 ms 35552 KB Output is correct
5 Correct 17 ms 35572 KB Output is correct
6 Correct 16 ms 35464 KB Output is correct
7 Correct 16 ms 35544 KB Output is correct
8 Correct 16 ms 35564 KB Output is correct
9 Correct 22 ms 35472 KB Output is correct
10 Correct 16 ms 35540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 16 ms 35540 KB Output is correct
3 Correct 15 ms 35524 KB Output is correct
4 Correct 17 ms 35552 KB Output is correct
5 Correct 17 ms 35572 KB Output is correct
6 Correct 16 ms 35464 KB Output is correct
7 Correct 16 ms 35544 KB Output is correct
8 Correct 16 ms 35564 KB Output is correct
9 Correct 22 ms 35472 KB Output is correct
10 Correct 16 ms 35540 KB Output is correct
11 Correct 251 ms 53260 KB Output is correct
12 Correct 253 ms 53116 KB Output is correct
13 Correct 252 ms 53164 KB Output is correct
14 Correct 288 ms 53220 KB Output is correct
15 Correct 249 ms 53360 KB Output is correct
16 Correct 268 ms 52608 KB Output is correct
17 Correct 267 ms 52696 KB Output is correct
18 Correct 264 ms 52520 KB Output is correct
19 Correct 247 ms 53124 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 59860 KB Output is correct
2 Correct 90 ms 58244 KB Output is correct
3 Correct 88 ms 56820 KB Output is correct
4 Correct 155 ms 59808 KB Output is correct
5 Correct 150 ms 59856 KB Output is correct
6 Correct 145 ms 59812 KB Output is correct
7 Correct 142 ms 59864 KB Output is correct
8 Correct 145 ms 59864 KB Output is correct
9 Correct 147 ms 59836 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 16 ms 35540 KB Output is correct
3 Correct 15 ms 35524 KB Output is correct
4 Correct 17 ms 35552 KB Output is correct
5 Correct 17 ms 35572 KB Output is correct
6 Correct 16 ms 35464 KB Output is correct
7 Correct 16 ms 35544 KB Output is correct
8 Correct 16 ms 35564 KB Output is correct
9 Correct 22 ms 35472 KB Output is correct
10 Correct 16 ms 35540 KB Output is correct
11 Correct 251 ms 53260 KB Output is correct
12 Correct 253 ms 53116 KB Output is correct
13 Correct 252 ms 53164 KB Output is correct
14 Correct 288 ms 53220 KB Output is correct
15 Correct 249 ms 53360 KB Output is correct
16 Correct 268 ms 52608 KB Output is correct
17 Correct 267 ms 52696 KB Output is correct
18 Correct 264 ms 52520 KB Output is correct
19 Correct 247 ms 53124 KB Output is correct
20 Correct 160 ms 59860 KB Output is correct
21 Correct 90 ms 58244 KB Output is correct
22 Correct 88 ms 56820 KB Output is correct
23 Correct 155 ms 59808 KB Output is correct
24 Correct 150 ms 59856 KB Output is correct
25 Correct 145 ms 59812 KB Output is correct
26 Correct 142 ms 59864 KB Output is correct
27 Correct 145 ms 59864 KB Output is correct
28 Correct 147 ms 59836 KB Output is correct
29 Correct 855 ms 118692 KB Output is correct
30 Correct 796 ms 117212 KB Output is correct
31 Correct 745 ms 117200 KB Output is correct
32 Correct 898 ms 123092 KB Output is correct
33 Correct 861 ms 123088 KB Output is correct
34 Correct 857 ms 120712 KB Output is correct
35 Correct 919 ms 120428 KB Output is correct
36 Correct 878 ms 120512 KB Output is correct
37 Correct 881 ms 121900 KB Output is correct
38 Correct 646 ms 127780 KB Output is correct
39 Correct 708 ms 127836 KB Output is correct
40 Correct 671 ms 124512 KB Output is correct
41 Correct 736 ms 123932 KB Output is correct
42 Correct 792 ms 124004 KB Output is correct
43 Correct 774 ms 125700 KB Output is correct
44 Correct 812 ms 127216 KB Output is correct
45 Correct 769 ms 127228 KB Output is correct
46 Correct 664 ms 124068 KB Output is correct
47 Correct 787 ms 123664 KB Output is correct
48 Correct 712 ms 123676 KB Output is correct
49 Correct 685 ms 125756 KB Output is correct
50 Correct 797 ms 125500 KB Output is correct
51 Correct 795 ms 125164 KB Output is correct
52 Correct 868 ms 122964 KB Output is correct
53 Correct 794 ms 122264 KB Output is correct
54 Correct 779 ms 121380 KB Output is correct
55 Correct 737 ms 121036 KB Output is correct