oj.uz

Submission #495612

# Submission time Handle Problem Language Result Execution time Memory
495612 2021-12-19T13:15:17 Z 600Mihnea Triple Jump (JOI19_jumps) C++17
100 / 100
 988 ms 123888 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 5e5 + 7;
const int K = 19;
const int INF = (int) 1e9 + 7;
int n;
int q;
int a[N];
int lg[N];
int maxA[K][N];
int nextBigger[N];

int getMaxA(int l, int r) {
  if (l > r) {
    return -INF;
  }
  assert(1 <= l && l <= r && r <= n);
  int k = lg[r - l + 1];
  return max(maxA[k][l], maxA[k][r - (1 << k) + 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 = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    maxA[0][i] = a[i];
  }
  build(1, 1, n);
  for (int k = 1; (1 << k) <= n; k++) {
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      maxA[k][i] = max(maxA[k - 1][i], maxA[k - 1][i + (1 << (k - 1))]);
    }
  }

  { /// just some stack bro
    vector<int> stk;
    for (int i = n; i >= 1; i--) {
      while (!stk.empty() && a[i] >= a[stk.back()]) {
        stk.pop_back();
      }
      nextBigger[i] = (stk.empty() ? (n + 1) : stk.back());
      stk.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> solPrint(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]) {
      solPrint[it.ind] = get(1, 1, n, l, it.r).maxAB;
    }
  }

  for (auto &x : solPrint) {
    assert(x != -1);
    cout << x << "\n";
  }



  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35544 KB Output is correct
2 Correct 19 ms 35624 KB Output is correct
3 Correct 18 ms 35532 KB Output is correct
4 Correct 18 ms 35504 KB Output is correct
5 Correct 20 ms 35524 KB Output is correct
6 Correct 24 ms 35660 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Correct 18 ms 35532 KB Output is correct
9 Correct 17 ms 35532 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35544 KB Output is correct
2 Correct 19 ms 35624 KB Output is correct
3 Correct 18 ms 35532 KB Output is correct
4 Correct 18 ms 35504 KB Output is correct
5 Correct 20 ms 35524 KB Output is correct
6 Correct 24 ms 35660 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Correct 18 ms 35532 KB Output is correct
9 Correct 17 ms 35532 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 295 ms 54952 KB Output is correct
12 Correct 288 ms 53416 KB Output is correct
13 Correct 331 ms 53468 KB Output is correct
14 Correct 287 ms 53600 KB Output is correct
15 Correct 305 ms 53668 KB Output is correct
16 Correct 295 ms 53036 KB Output is correct
17 Correct 293 ms 53024 KB Output is correct
18 Correct 286 ms 52868 KB Output is correct
19 Correct 307 ms 53476 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 58184 KB Output is correct
2 Correct 106 ms 56720 KB Output is correct
3 Correct 103 ms 55244 KB Output is correct
4 Correct 175 ms 58304 KB Output is correct
5 Correct 170 ms 58292 KB Output is correct
6 Correct 163 ms 58180 KB Output is correct
7 Correct 178 ms 58124 KB Output is correct
8 Correct 183 ms 58192 KB Output is correct
9 Correct 162 ms 58168 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35544 KB Output is correct
2 Correct 19 ms 35624 KB Output is correct
3 Correct 18 ms 35532 KB Output is correct
4 Correct 18 ms 35504 KB Output is correct
5 Correct 20 ms 35524 KB Output is correct
6 Correct 24 ms 35660 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Correct 18 ms 35532 KB Output is correct
9 Correct 17 ms 35532 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 295 ms 54952 KB Output is correct
12 Correct 288 ms 53416 KB Output is correct
13 Correct 331 ms 53468 KB Output is correct
14 Correct 287 ms 53600 KB Output is correct
15 Correct 305 ms 53668 KB Output is correct
16 Correct 295 ms 53036 KB Output is correct
17 Correct 293 ms 53024 KB Output is correct
18 Correct 286 ms 52868 KB Output is correct
19 Correct 307 ms 53476 KB Output is correct
20 Correct 182 ms 58184 KB Output is correct
21 Correct 106 ms 56720 KB Output is correct
22 Correct 103 ms 55244 KB Output is correct
23 Correct 175 ms 58304 KB Output is correct
24 Correct 170 ms 58292 KB Output is correct
25 Correct 163 ms 58180 KB Output is correct
26 Correct 178 ms 58124 KB Output is correct
27 Correct 183 ms 58192 KB Output is correct
28 Correct 162 ms 58168 KB Output is correct
29 Correct 974 ms 119180 KB Output is correct
30 Correct 837 ms 113188 KB Output is correct
31 Correct 822 ms 113084 KB Output is correct
32 Correct 988 ms 119176 KB Output is correct
33 Correct 984 ms 119152 KB Output is correct
34 Correct 968 ms 116856 KB Output is correct
35 Correct 975 ms 116540 KB Output is correct
36 Correct 983 ms 116540 KB Output is correct
37 Correct 988 ms 117892 KB Output is correct
38 Correct 787 ms 123804 KB Output is correct
39 Correct 746 ms 123888 KB Output is correct
40 Correct 735 ms 120620 KB Output is correct
41 Correct 776 ms 119900 KB Output is correct
42 Correct 771 ms 119916 KB Output is correct
43 Correct 799 ms 121752 KB Output is correct
44 Correct 831 ms 123200 KB Output is correct
45 Correct 793 ms 123244 KB Output is correct
46 Correct 771 ms 120080 KB Output is correct
47 Correct 749 ms 119648 KB Output is correct
48 Correct 768 ms 119636 KB Output is correct
49 Correct 741 ms 121700 KB Output is correct
50 Correct 819 ms 121500 KB Output is correct
51 Correct 821 ms 121668 KB Output is correct
52 Correct 824 ms 118940 KB Output is correct
53 Correct 825 ms 118828 KB Output is correct
54 Correct 805 ms 118652 KB Output is correct
55 Correct 843 ms 120272 KB Output is correct