oj.uz

Submission #225385

# Submission time Handle Problem Language Result Execution time Memory
225385 2020-04-20T12:50:36 Z Bruteforceman Triple Jump (JOI19_jumps) C++11
100 / 100
 2961 ms 102228 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int a[maxn];
vector <int> qr[maxn];
vector <pair <int, int>> v[maxn];
int res[maxn], opt[maxn];
int l[maxn], r[maxn];
int n;

struct node {
  int mxpair, maxv, opt;
  node () {}
  node (int mxpair, int maxv, int opt) : mxpair(mxpair), maxv(maxv), opt(opt) {}
};
node operator + (node p, node q) {
  node ans;
  ans.maxv = max(p.maxv, q.maxv);
  ans.mxpair = max(p.mxpair, q.mxpair);
  ans.opt = max(p.opt, q.opt);
  ans.opt = max(ans.opt, p.mxpair + q.maxv);
  return ans;
}
node t[maxn * 4];
void build(int c = 1, int b = 1, int e = n) {
  if(b == e) {
    t[c].mxpair = 0;
    t[c].opt = t[c].maxv = a[b];
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  build(l, b, m);
  build(r, m + 1, e);
  t[c] = t[l] + t[r];
}
void update(int x, int val, int c = 1, int b = 1, int e = n) {
  if(b == e) {
    t[c].mxpair = max(t[c].mxpair, val);
    t[c].opt = t[c].mxpair + t[c].maxv;
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) update(x, val, l, b, m);
  else update(x, val, r, m + 1, e);
  t[c] = t[l] + t[r];
}
node query(int x, int y, int c = 1, int b = 1, int e = n) {
  if(x <= b && e <= y) {
    return t[c];
  }
  if(y < b || e < x) return node( 0, 0, 0);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return query(x, y, l, b, m) + query(x, y, r, m + 1, e);
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int q;
  cin >> q;
  for(int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    qr[l[i]].emplace_back(i);
  }
  stack <int> s;
  vector <pair <int, int>> imp;
  for(int i = 1; i <= n; i++) {
    while(!s.empty() && a[s.top()] <= a[i]) {
      imp.emplace_back(s.top(), i);
      s.pop();
    }
    if(!s.empty()) imp.emplace_back(s.top(), i);
    s.push(i);
  }
  for(auto i : imp) {
    if(2 * i.second - i.first <= n) {
      v[i.first].emplace_back(2 * i.second - i.first, 
          a[i.first] + a[i.second]);
    }
  }
  build();
  for(int i = n; i >= 1; i--) {
    for(auto j : v[i]) {
      if(j.first <= n) {
        update(j.first, j.second);
      }
    }
    for(auto j : qr[i]) {
      res[j] = query(l[j], r[j]).opt;
    }
  }
  for(int i = 1; i <= q; i++) {
    cout << res[i] << endl;
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 19 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 19 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct
11 Correct 1572 ms 43384 KB Output is correct
12 Correct 1556 ms 43128 KB Output is correct
13 Correct 1615 ms 43128 KB Output is correct
14 Correct 1556 ms 43240 KB Output is correct
15 Correct 1578 ms 43128 KB Output is correct
16 Correct 1533 ms 42616 KB Output is correct
17 Correct 1621 ms 42488 KB Output is correct
18 Correct 1576 ms 42596 KB Output is correct
19 Correct 1558 ms 43232 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 43228 KB Output is correct
2 Correct 212 ms 40400 KB Output is correct
3 Correct 217 ms 41192 KB Output is correct
4 Correct 297 ms 43316 KB Output is correct
5 Correct 292 ms 43100 KB Output is correct
6 Correct 271 ms 42460 KB Output is correct
7 Correct 263 ms 42460 KB Output is correct
8 Correct 261 ms 42448 KB Output is correct
9 Correct 280 ms 42716 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 19 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct
11 Correct 1572 ms 43384 KB Output is correct
12 Correct 1556 ms 43128 KB Output is correct
13 Correct 1615 ms 43128 KB Output is correct
14 Correct 1556 ms 43240 KB Output is correct
15 Correct 1578 ms 43128 KB Output is correct
16 Correct 1533 ms 42616 KB Output is correct
17 Correct 1621 ms 42488 KB Output is correct
18 Correct 1576 ms 42596 KB Output is correct
19 Correct 1558 ms 43232 KB Output is correct
20 Correct 298 ms 43228 KB Output is correct
21 Correct 212 ms 40400 KB Output is correct
22 Correct 217 ms 41192 KB Output is correct
23 Correct 297 ms 43316 KB Output is correct
24 Correct 292 ms 43100 KB Output is correct
25 Correct 271 ms 42460 KB Output is correct
26 Correct 263 ms 42460 KB Output is correct
27 Correct 261 ms 42448 KB Output is correct
28 Correct 280 ms 42716 KB Output is correct
29 Correct 2811 ms 95668 KB Output is correct
30 Correct 2518 ms 88728 KB Output is correct
31 Correct 2555 ms 90592 KB Output is correct
32 Correct 2721 ms 95560 KB Output is correct
33 Correct 2961 ms 95704 KB Output is correct
34 Correct 2781 ms 93648 KB Output is correct
35 Correct 2666 ms 93136 KB Output is correct
36 Correct 2640 ms 93004 KB Output is correct
37 Correct 2671 ms 94740 KB Output is correct
38 Correct 2439 ms 102228 KB Output is correct
39 Correct 2447 ms 102160 KB Output is correct
40 Correct 2397 ms 99028 KB Output is correct
41 Correct 2362 ms 98472 KB Output is correct
42 Correct 2382 ms 98516 KB Output is correct
43 Correct 2360 ms 100180 KB Output is correct
44 Correct 2461 ms 101596 KB Output is correct
45 Correct 2531 ms 101680 KB Output is correct
46 Correct 2368 ms 98384 KB Output is correct
47 Correct 2362 ms 98036 KB Output is correct
48 Correct 2361 ms 98132 KB Output is correct
49 Correct 2433 ms 100188 KB Output is correct
50 Correct 2578 ms 99440 KB Output is correct
51 Correct 2532 ms 99540 KB Output is correct
52 Correct 2537 ms 97088 KB Output is correct
53 Correct 2499 ms 96624 KB Output is correct
54 Correct 2554 ms 96596 KB Output is correct
55 Correct 2549 ms 98300 KB Output is correct