oj.uz

Submission #768372

# Submission time Handle Problem Language Result Execution time Memory
768372 2023-06-28T02:43:45 Z hazzle Triple Jump (JOI19_jumps) C++17
100 / 100
 906 ms 126372 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("avx2")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const int N = 5e5 + 42;

struct node{
      ll mx, ans, p;
      node(ll mx = 0): mx(mx), ans(0), p(0) {}
      node operator+(node o){
            node res;
            res.mx = max(mx, o.mx);
            res.ans = max(ans, o.ans);
            return res;
      }
} t[4 * N];

void build(int tl, int tr, int v, vec <ll> &a){
      if (tl + 1 == tr) return void(t[v] = a[tl]);
      int tm = tl + tr >> 1;
      build(tl, tm, v * 2 + 1, a);
      build(tm, tr, v * 2 + 2, a);
      t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

void apply(int v, ll x){
      umax(t[v].ans, t[v].mx + x);
      umax(t[v].p, x);
}

void push(int v){
      if (!t[v].p) return;
      for (int i: {v * 2 + 1, v * 2 + 2}){
            apply(i, t[v].p);
      }
      t[v].p = 0;
}

void upd(int l, int r, ll x, int tl, int tr, int v){
      if (l >= r) return;
      if (tl == l && tr == r) return void(apply(v, x));
      push(v);
      int tm = tl + tr >> 1;
      upd(l, min(tm, r), x, tl, tm, v * 2 + 1);
      upd(max(l, tm), r, x, tm, tr, v * 2 + 2);
      t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

ll get(int l, int r, int tl, int tr, int v){
      if (l >= r) return 0LL;
      if (tl == l && tr == r) return t[v].ans;
      push(v);
      int tm = tl + tr >> 1;
      return max(get(l, min(tm, r), tl, tm, v * 2 + 1),
                 get(max(l, tm), r, tm, tr, v * 2 + 2));
}

inline int solve(){
      int n; cin >> n;
      vec <ll> a(n);
      for (auto &i: a) cin >> i;
      int q; cin >> q;
      vec <vec <pii>> qq(n);
      for (int i = 0; i < q; ++i){
            int l, r;
            cin >> l >> r, --l;
            qq[l].push_back({r, i});
      }
      vec <vec <int>> qu(n);
      vec <int> st;
      for (int i = 0; i < n; ++i){
            while(!st.empty() && a[st.back()] < a[i]){
                  st.pop_back();
            }
            if (!st.empty()){
                  qu[st.back()].push_back(i);
            }
            st.push_back(i);
      }
      st.clear();
      for (int i = n - 1; ~i; --i){
            while(!st.empty() && a[st.back()] < a[i]){
                  st.pop_back();
            }
            if (!st.empty()){
                  qu[i].push_back(st.back());
            }
            st.push_back(i);
      }
      build(0, n, 0, a);
      vec <ll> ans(q);
      for (int l = n - 1; ~l; --l){
            for (auto &r: qu[l]){
                  upd(2 * r - l, n, a[l] + a[r], 0, n, 0);
            }
            for (auto &[r, id]: qq[l]){
                  ans[id] = get(0, r, 0, n, 0);
            }
      }
      for (auto &i: ans){
            cout << i << "\n";
      }
      return 0;
}

inline void precalc(){}

signed main(){
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tst = 1; //cin >> tst;
      precalc();
      while(tst--) solve();
      return 0;
}

Compilation message

jumps.cpp: In function 'void build(int, int, int, std::vector<long long int>&)':
jumps.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
jumps.cpp: In function 'void upd(int, int, ll, int, int, int)':
jumps.cpp:73:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
jumps.cpp: In function 'll get(int, int, int, int, int)':
jumps.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |       int tm = tl + tr >> 1;
      |                ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 18 ms 47268 KB Output is correct
3 Correct 19 ms 47216 KB Output is correct
4 Correct 22 ms 47180 KB Output is correct
5 Correct 18 ms 47304 KB Output is correct
6 Correct 19 ms 47188 KB Output is correct
7 Correct 18 ms 47244 KB Output is correct
8 Correct 18 ms 47284 KB Output is correct
9 Correct 19 ms 47232 KB Output is correct
10 Correct 19 ms 47256 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 18 ms 47268 KB Output is correct
3 Correct 19 ms 47216 KB Output is correct
4 Correct 22 ms 47180 KB Output is correct
5 Correct 18 ms 47304 KB Output is correct
6 Correct 19 ms 47188 KB Output is correct
7 Correct 18 ms 47244 KB Output is correct
8 Correct 18 ms 47284 KB Output is correct
9 Correct 19 ms 47232 KB Output is correct
10 Correct 19 ms 47256 KB Output is correct
11 Correct 190 ms 68172 KB Output is correct
12 Correct 190 ms 68044 KB Output is correct
13 Correct 180 ms 68048 KB Output is correct
14 Correct 187 ms 68052 KB Output is correct
15 Correct 192 ms 68184 KB Output is correct
16 Correct 192 ms 67404 KB Output is correct
17 Correct 189 ms 67356 KB Output is correct
18 Correct 194 ms 67400 KB Output is correct
19 Correct 197 ms 67944 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 64724 KB Output is correct
2 Correct 82 ms 65236 KB Output is correct
3 Correct 80 ms 65260 KB Output is correct
4 Correct 144 ms 64716 KB Output is correct
5 Correct 147 ms 64724 KB Output is correct
6 Correct 136 ms 64720 KB Output is correct
7 Correct 141 ms 64604 KB Output is correct
8 Correct 134 ms 65704 KB Output is correct
9 Correct 139 ms 65996 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 18 ms 47268 KB Output is correct
3 Correct 19 ms 47216 KB Output is correct
4 Correct 22 ms 47180 KB Output is correct
5 Correct 18 ms 47304 KB Output is correct
6 Correct 19 ms 47188 KB Output is correct
7 Correct 18 ms 47244 KB Output is correct
8 Correct 18 ms 47284 KB Output is correct
9 Correct 19 ms 47232 KB Output is correct
10 Correct 19 ms 47256 KB Output is correct
11 Correct 190 ms 68172 KB Output is correct
12 Correct 190 ms 68044 KB Output is correct
13 Correct 180 ms 68048 KB Output is correct
14 Correct 187 ms 68052 KB Output is correct
15 Correct 192 ms 68184 KB Output is correct
16 Correct 192 ms 67404 KB Output is correct
17 Correct 189 ms 67356 KB Output is correct
18 Correct 194 ms 67400 KB Output is correct
19 Correct 197 ms 67944 KB Output is correct
20 Correct 142 ms 64724 KB Output is correct
21 Correct 82 ms 65236 KB Output is correct
22 Correct 80 ms 65260 KB Output is correct
23 Correct 144 ms 64716 KB Output is correct
24 Correct 147 ms 64724 KB Output is correct
25 Correct 136 ms 64720 KB Output is correct
26 Correct 141 ms 64604 KB Output is correct
27 Correct 134 ms 65704 KB Output is correct
28 Correct 139 ms 65996 KB Output is correct
29 Correct 803 ms 120792 KB Output is correct
30 Correct 642 ms 122040 KB Output is correct
31 Correct 575 ms 122020 KB Output is correct
32 Correct 800 ms 120660 KB Output is correct
33 Correct 779 ms 120656 KB Output is correct
34 Correct 823 ms 118428 KB Output is correct
35 Correct 819 ms 118044 KB Output is correct
36 Correct 883 ms 118044 KB Output is correct
37 Correct 906 ms 119488 KB Output is correct
38 Correct 598 ms 126356 KB Output is correct
39 Correct 541 ms 126372 KB Output is correct
40 Correct 547 ms 123020 KB Output is correct
41 Correct 554 ms 122496 KB Output is correct
42 Correct 554 ms 122568 KB Output is correct
43 Correct 545 ms 124284 KB Output is correct
44 Correct 588 ms 125736 KB Output is correct
45 Correct 632 ms 125756 KB Output is correct
46 Correct 578 ms 122608 KB Output is correct
47 Correct 579 ms 122124 KB Output is correct
48 Correct 580 ms 122176 KB Output is correct
49 Correct 569 ms 124324 KB Output is correct
50 Correct 636 ms 123680 KB Output is correct
51 Correct 629 ms 123784 KB Output is correct
52 Correct 612 ms 121148 KB Output is correct
53 Correct 609 ms 120896 KB Output is correct
54 Correct 610 ms 120792 KB Output is correct
55 Correct 633 ms 122536 KB Output is correct