oj.uz

Submission #532721

# Submission time Handle Problem Language Result Execution time Memory
532721 2022-03-03T18:17:52 Z Alex_tz307 Triple Jump (JOI19_jumps) C++17
100 / 100
 1073 ms 63896 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int kN = 5e5;
int a[1 + kN], s1[1 + kN], s2[1 + kN], dr1[1 + kN], dr2[1 + kN], sol[kN];
vector<pair<int, int>> q[1 + kN];

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> maxSum, tmax, best;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    dim *= 2;
    maxSum.resize(dim, -INF);
    tmax.resize(dim);
    best.resize(dim, -INF);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      tmax[x] = a[lx];
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
    tmax[x] = max(tmax[x * 2], tmax[x * 2 + 1]);
  }

  void push(int x, int lx, int rx) {
    if (lx == rx) {
      return;
    }
    for (int i = 0; i < 2; ++i) {
      maxSelf(maxSum[x * 2 + i], maxSum[x]);
      maxSelf(best[x * 2 + i], maxSum[x * 2 + i] + tmax[x * 2 + i]);
    }
    maxSelf(best[x], max(best[x * 2], best[x * 2 + 1]));
  }

  void update(int x, int lx, int rx, int st, int dr, int sum) {
    if (st <= lx && rx <= dr) {
      maxSelf(maxSum[x], sum);
      maxSelf(best[x], maxSum[x] + tmax[x]);
      push(x, lx, rx);
      return;
    }
    push(x, lx, rx);
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, sum);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, sum);
    }
    maxSelf(best[x], max(best[x * 2], best[x * 2 + 1]));
  }

  void update(int st, int dr, int sum) {
    if (dr < st) {
      return;
    }
    update(1, 1, n, st, dr, sum);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    push(x, lx, rx);
    if (st <= lx && rx <= dr) {
      return best[x];
    }
    int mid = (lx + rx) / 2, ans = 0;
    if (st <= mid) {
      maxSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void testCase() {
  int n;
  cin >> n;
  int vf1 = 0, vf2 = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    while (vf1 && a[s1[vf1]] <= a[i]) {
      dr1[s1[vf1]] = i;
      vf1 -= 1;
    }
    while (vf2 && a[s2[vf2]] < a[i]) {
      dr2[s2[vf2]] = i;
      vf2 -= 1;
    }
    s1[++vf1] = i;
    s2[++vf2] = i;
    dr1[i] = dr2[i] = n + 1;
  }
  ST t(n);
  t.build(1, 1, n);
  int m;
  cin >> m;
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    q[l].emplace_back(r, i);
  }
  for (int i = n - 2; i > 0; --i) {
    int j = i + 1;
    while (j <= n && j <= dr1[i]) {
      t.update(2 * j - i, n, a[i] + a[j]);
      j = dr2[j];
    }
    for (auto it : q[i]) {
      int k, index;
      tie(k, index) = it;
      sol[index] = t.query(i + 2, k);
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << sol[i] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Correct 7 ms 12072 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12064 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 7 ms 12068 KB Output is correct
8 Correct 7 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12068 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Correct 7 ms 12072 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12064 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 7 ms 12068 KB Output is correct
8 Correct 7 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12068 KB Output is correct
11 Correct 326 ms 30968 KB Output is correct
12 Correct 290 ms 30820 KB Output is correct
13 Correct 283 ms 30864 KB Output is correct
14 Correct 299 ms 30900 KB Output is correct
15 Correct 272 ms 31000 KB Output is correct
16 Correct 292 ms 30276 KB Output is correct
17 Correct 299 ms 30196 KB Output is correct
18 Correct 278 ms 30240 KB Output is correct
19 Correct 270 ms 30832 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 22356 KB Output is correct
2 Correct 89 ms 22356 KB Output is correct
3 Correct 106 ms 23920 KB Output is correct
4 Correct 155 ms 22236 KB Output is correct
5 Correct 145 ms 22352 KB Output is correct
6 Correct 149 ms 21700 KB Output is correct
7 Correct 148 ms 21492 KB Output is correct
8 Correct 144 ms 21700 KB Output is correct
9 Correct 140 ms 21924 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 7 ms 12068 KB Output is correct
3 Correct 7 ms 12072 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12064 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 7 ms 12068 KB Output is correct
8 Correct 7 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12068 KB Output is correct
11 Correct 326 ms 30968 KB Output is correct
12 Correct 290 ms 30820 KB Output is correct
13 Correct 283 ms 30864 KB Output is correct
14 Correct 299 ms 30900 KB Output is correct
15 Correct 272 ms 31000 KB Output is correct
16 Correct 292 ms 30276 KB Output is correct
17 Correct 299 ms 30196 KB Output is correct
18 Correct 278 ms 30240 KB Output is correct
19 Correct 270 ms 30832 KB Output is correct
20 Correct 160 ms 22356 KB Output is correct
21 Correct 89 ms 22356 KB Output is correct
22 Correct 106 ms 23920 KB Output is correct
23 Correct 155 ms 22236 KB Output is correct
24 Correct 145 ms 22352 KB Output is correct
25 Correct 149 ms 21700 KB Output is correct
26 Correct 148 ms 21492 KB Output is correct
27 Correct 144 ms 21700 KB Output is correct
28 Correct 140 ms 21924 KB Output is correct
29 Correct 972 ms 58052 KB Output is correct
30 Correct 783 ms 57956 KB Output is correct
31 Correct 839 ms 61932 KB Output is correct
32 Correct 1000 ms 58192 KB Output is correct
33 Correct 1018 ms 58084 KB Output is correct
34 Correct 945 ms 55812 KB Output is correct
35 Correct 980 ms 55520 KB Output is correct
36 Correct 967 ms 55436 KB Output is correct
37 Correct 1073 ms 57024 KB Output is correct
38 Correct 738 ms 63788 KB Output is correct
39 Correct 758 ms 63896 KB Output is correct
40 Correct 696 ms 60464 KB Output is correct
41 Correct 750 ms 59888 KB Output is correct
42 Correct 721 ms 59996 KB Output is correct
43 Correct 715 ms 61636 KB Output is correct
44 Correct 788 ms 63136 KB Output is correct
45 Correct 779 ms 63156 KB Output is correct
46 Correct 762 ms 59992 KB Output is correct
47 Correct 748 ms 59628 KB Output is correct
48 Correct 782 ms 59612 KB Output is correct
49 Correct 771 ms 61692 KB Output is correct
50 Correct 847 ms 61284 KB Output is correct
51 Correct 828 ms 61212 KB Output is correct
52 Correct 808 ms 58720 KB Output is correct
53 Correct 809 ms 58516 KB Output is correct
54 Correct 809 ms 58524 KB Output is correct
55 Correct 838 ms 60284 KB Output is correct