oj.uz

Submission #168161

# Submission time Handle Problem Language Result Execution time Memory
168161 2019-12-11T17:13:44 Z AlexPop28 Triple Jump (JOI19_jumps) C++11
100 / 100
 1531 ms 101088 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
// dupa 7 ore printre care 3 de somn in care ma tot gandeam de ce luasem
// RTE, am ajuns la concluzia ca e din cauza stupizeniei de windows...
 
using namespace std;
 
struct SegmTree {
  struct Node {
    int maxv, val, lazy;
    Node(int maxv_ = 0, int val_ = 0, int lazy_ = 0) :
      maxv(maxv_), val(val_), lazy(lazy_) {}
    // maxv = val max on [l, r] in v
    // val = maximum val of jumps in [l, r]
    // lazy = max val to update children with
  };
  int n;
  vector<int> v;
  vector<Node> tree;
  SegmTree(const vector<int> v_) : n(v_.size()), v(v_), tree(4 * n) {
    Build(0, 0, n - 1);
  }
  void Recalc(int node) {
    tree[node].val = max(tree[2 * node + 1].val, tree[2 * node + 2].val);
  }
  void Build(int node, int left, int right) {
    if (left == right) {
      tree[node].maxv = v[left];
      tree[node].val = v[left];
      tree[node].lazy = 0;
      return;
    }
    int mid = left + (right - left) / 2;
    Build(2 * node + 1, left, mid);
    Build(2 * node + 2, mid + 1, right);
    tree[node].maxv = max(tree[2 * node + 1].maxv, tree[2 * node + 2].maxv);
    Recalc(node);
  }
  void Propagate(int node, int len) {
    if (len == 1) return;
    for (int son : {2 * node + 1, 2 * node + 2}) {
      tree[son].lazy = max(tree[son].lazy, tree[node].lazy);
      tree[son].val = max(tree[son].val, tree[son].maxv + tree[son].lazy); 
    }
  }
  void Update(int node, int left, int right, int x, int y, int val) {
    Propagate(node, right - left + 1);
    if (x <= left && right <= y) {
      tree[node].val = max(tree[node].val, tree[node].maxv + val);
      tree[node].lazy = max(tree[node].lazy, val);
//      dbg() "Am setat: " << name(left) name(right) name(tree[node].val) endl;
      return;
    }
    int mid = left + (right - left) / 2;
    if (x <= mid)
      Update(2 * node + 1, left, mid, x, y, val);
    if (mid < y)
      Update(2 * node + 2, mid + 1, right, x, y, val);
    Recalc(node);
  }
  int Query(int node, int left, int right, int x, int y) {
    Propagate(node, right - left + 1);
    if (x <= left && right <= y) {
      return tree[node].val;
    }
    int mid = left + (right - left) / 2;
    int ret = 0;
    if (x <= mid)
      ret = max(ret, Query(2 * node + 1, left, mid, x, y));
    if (mid < y)
      ret = max(ret, Query(2 * node + 2, mid + 1, right, x, y));
    Recalc(node);
    return ret;
  }
  void Update(int l, int r, int val) {
    if (l > r) return;
//    dbg() "U: " << name(l) name(r) name(val) endl;
    Update(0, 0, n - 1, l, r, val);
  }
  int Query(int l, int r) {
//    dbg() "Q: " << name(l) name(r) endl;
    return Query(0, 0, n - 1, l, r);
  }
};
 
vector<vector<int>> GetAdd(const vector<int> &v) {
  int n = v.size();
  vector<int> stk = {-1}, lft(n), rgt(n);
  for (int i = 0; i < n; ++i) {
    while (stk.size() > 1 && v[stk.back()] < v[i]) {
      rgt[stk.back()] = i;
      stk.pop_back();
    }
    lft[i] = stk.back();
    stk.emplace_back(i);
  }
  while (stk.size() > 1) {
    rgt[stk.back()] = n;
    stk.pop_back();
  }
  vector<vector<int>> to_add(n);
  for (int i = 0; i < n; ++i) {
    if (lft[i] != -1) {
      to_add[lft[i]].emplace_back(i);
    }
    if (rgt[i] != n) {
      to_add[i].emplace_back(rgt[i]);
    }
  }
  return to_add;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
 
  int n; cin >> n;
  vector<int> v(n);
  for (int &x : v) {
    cin >> x;
  }
 
  int q; cin >> q;
  vector<vector<pair<int, int>>> qrs(n);
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r; --l, --r;
    qrs[l].emplace_back(r, i);
  }
 
  auto to_add = GetAdd(v);
  SegmTree tree(v);
  vector<int> ans(q);
  for (int l = n - 1; l >= 0; --l) {
    for (int &x : to_add[l]) {
      tree.Update(x + x - l, n - 1, v[l] + v[x]);
    }
    for (auto &p : qrs[l]) {
      ans[p.second] = tree.Query(l, p.first); 
    }
  }
  for (int &x : ans) {
    cout << x << '\n';
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 423 ms 18984 KB Output is correct
12 Correct 421 ms 18936 KB Output is correct
13 Correct 426 ms 19020 KB Output is correct
14 Correct 420 ms 19064 KB Output is correct
15 Correct 421 ms 19064 KB Output is correct
16 Correct 422 ms 18324 KB Output is correct
17 Correct 420 ms 18296 KB Output is correct
18 Correct 445 ms 18340 KB Output is correct
19 Correct 428 ms 18780 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 29784 KB Output is correct
2 Correct 140 ms 29656 KB Output is correct
3 Correct 143 ms 29472 KB Output is correct
4 Correct 232 ms 29784 KB Output is correct
5 Correct 235 ms 29872 KB Output is correct
6 Correct 227 ms 29160 KB Output is correct
7 Correct 226 ms 29016 KB Output is correct
8 Correct 228 ms 29016 KB Output is correct
9 Correct 232 ms 29272 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 423 ms 18984 KB Output is correct
12 Correct 421 ms 18936 KB Output is correct
13 Correct 426 ms 19020 KB Output is correct
14 Correct 420 ms 19064 KB Output is correct
15 Correct 421 ms 19064 KB Output is correct
16 Correct 422 ms 18324 KB Output is correct
17 Correct 420 ms 18296 KB Output is correct
18 Correct 445 ms 18340 KB Output is correct
19 Correct 428 ms 18780 KB Output is correct
20 Correct 233 ms 29784 KB Output is correct
21 Correct 140 ms 29656 KB Output is correct
22 Correct 143 ms 29472 KB Output is correct
23 Correct 232 ms 29784 KB Output is correct
24 Correct 235 ms 29872 KB Output is correct
25 Correct 227 ms 29160 KB Output is correct
26 Correct 226 ms 29016 KB Output is correct
27 Correct 228 ms 29016 KB Output is correct
28 Correct 232 ms 29272 KB Output is correct
29 Correct 1463 ms 95416 KB Output is correct
30 Correct 1215 ms 94892 KB Output is correct
31 Correct 1223 ms 94712 KB Output is correct
32 Correct 1488 ms 95216 KB Output is correct
33 Correct 1484 ms 95356 KB Output is correct
34 Correct 1454 ms 93060 KB Output is correct
35 Correct 1470 ms 92792 KB Output is correct
36 Correct 1531 ms 92608 KB Output is correct
37 Correct 1485 ms 94288 KB Output is correct
38 Correct 1108 ms 101036 KB Output is correct
39 Correct 1117 ms 101088 KB Output is correct
40 Correct 1098 ms 97664 KB Output is correct
41 Correct 1088 ms 97212 KB Output is correct
42 Correct 1089 ms 97332 KB Output is correct
43 Correct 1097 ms 98776 KB Output is correct
44 Correct 1226 ms 100380 KB Output is correct
45 Correct 1204 ms 100436 KB Output is correct
46 Correct 1185 ms 97032 KB Output is correct
47 Correct 1186 ms 96800 KB Output is correct
48 Correct 1188 ms 96608 KB Output is correct
49 Correct 1193 ms 98932 KB Output is correct
50 Correct 1300 ms 98348 KB Output is correct
51 Correct 1309 ms 98040 KB Output is correct
52 Correct 1325 ms 95788 KB Output is correct
53 Correct 1348 ms 95476 KB Output is correct
54 Correct 1306 ms 95532 KB Output is correct
55 Correct 1339 ms 96824 KB Output is correct