oj.uz

Submission #139365

# Submission time Handle Problem Language Result Execution time Memory
139365 2019-07-31T15:19:14 Z IOrtroiii Triple Jump (JOI19_jumps) C++14
100 / 100
 1447 ms 136184 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 500500;
const ll inf = 1e18;

struct State {
   ll pref, suf, ans;
   State() : pref(-inf), suf(-inf), ans(-inf) {}
   friend State operator + (const State &l, const State &r) {
      State ans;
      ans.pref = max(l.pref, r.pref);
      ans.suf = max(l.suf, r.suf);
      ans.ans = max({l.ans, r.ans, l.pref + r.suf});
      return ans;
   }
};

ll a[N];
State t[N << 2];
ll ans[N];
vector<pair<int, ll>> es[N];
vector<pair<int, int>> qs[N];

void build(int v, int l, int r) {
   if (l == r) {
      t[v].suf = a[l];
      return;
   }
   int md = (l + r) >> 1;
   build(v << 1, l, md);
   build(v << 1 | 1, md + 1, r);
   t[v] = t[v << 1] + t[v << 1 | 1];
}

void mdf(int v, int l, int r, int p, ll val) {
   if (l == r) {
      t[v].pref = max(t[v].pref, val);
      return;
   }
   int md = (l + r) >> 1;
   if (p <= md) {
      mdf(v << 1, l, md, p, val);
   } else {
      mdf(v << 1 | 1, md + 1, r, p, val);
   }
   t[v] = t[v << 1] + t[v << 1 | 1];
}

State get(int v, int l, int r, int L, int R) {
   if (L > r || R < l) return State();
   if (L <= l && r <= R) {
      return t[v];
   }
   int md = (l + r) >> 1;
   return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   cin >> n;
   vector<int> st;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      while (!st.empty()) {
         int go = 2 * i - st.back() - 1;
         if (go < n) es[st.back()].emplace_back(a[i] + a[st.back()], go);
         if (a[i] < a[st.back()]) {
            break;
         } else {
            st.pop_back();
         }
      }
      st.emplace_back(i);
   }
   int q;
   cin >> q;
   for (int i = 1; i <= q; ++i) {
      int l, r;
      cin >> l >> r;
      qs[l].emplace_back(r, i);
   }
   build(1, 1, n);
   for (int i = n; i > 0; --i) {
      for (auto e : es[i]) {
         mdf(1, 1, n, e.second, e.first);
      }
      for (auto q : qs[i]) {
         ans[q.second] = get(1, 1, n, i, q.first).ans;
      }
   }
   for (int i = 1; i <= q; ++i) {
      cout << ans[i] << "\n";
   }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70904 KB Output is correct
2 Correct 62 ms 70904 KB Output is correct
3 Correct 63 ms 70904 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 63 ms 70904 KB Output is correct
6 Correct 63 ms 70904 KB Output is correct
7 Correct 63 ms 70904 KB Output is correct
8 Correct 64 ms 70904 KB Output is correct
9 Correct 63 ms 70892 KB Output is correct
10 Correct 63 ms 70876 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70904 KB Output is correct
2 Correct 62 ms 70904 KB Output is correct
3 Correct 63 ms 70904 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 63 ms 70904 KB Output is correct
6 Correct 63 ms 70904 KB Output is correct
7 Correct 63 ms 70904 KB Output is correct
8 Correct 64 ms 70904 KB Output is correct
9 Correct 63 ms 70892 KB Output is correct
10 Correct 63 ms 70876 KB Output is correct
11 Correct 498 ms 91328 KB Output is correct
12 Correct 476 ms 91028 KB Output is correct
13 Correct 471 ms 91128 KB Output is correct
14 Correct 477 ms 91256 KB Output is correct
15 Correct 486 ms 91200 KB Output is correct
16 Correct 478 ms 90616 KB Output is correct
17 Correct 481 ms 90548 KB Output is correct
18 Correct 481 ms 90596 KB Output is correct
19 Correct 478 ms 91128 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 84416 KB Output is correct
2 Correct 150 ms 80580 KB Output is correct
3 Correct 149 ms 81288 KB Output is correct
4 Correct 244 ms 84600 KB Output is correct
5 Correct 228 ms 84472 KB Output is correct
6 Correct 220 ms 83832 KB Output is correct
7 Correct 220 ms 83960 KB Output is correct
8 Correct 220 ms 83776 KB Output is correct
9 Correct 225 ms 83972 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70904 KB Output is correct
2 Correct 62 ms 70904 KB Output is correct
3 Correct 63 ms 70904 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 63 ms 70904 KB Output is correct
6 Correct 63 ms 70904 KB Output is correct
7 Correct 63 ms 70904 KB Output is correct
8 Correct 64 ms 70904 KB Output is correct
9 Correct 63 ms 70892 KB Output is correct
10 Correct 63 ms 70876 KB Output is correct
11 Correct 498 ms 91328 KB Output is correct
12 Correct 476 ms 91028 KB Output is correct
13 Correct 471 ms 91128 KB Output is correct
14 Correct 477 ms 91256 KB Output is correct
15 Correct 486 ms 91200 KB Output is correct
16 Correct 478 ms 90616 KB Output is correct
17 Correct 481 ms 90548 KB Output is correct
18 Correct 481 ms 90596 KB Output is correct
19 Correct 478 ms 91128 KB Output is correct
20 Correct 237 ms 84416 KB Output is correct
21 Correct 150 ms 80580 KB Output is correct
22 Correct 149 ms 81288 KB Output is correct
23 Correct 244 ms 84600 KB Output is correct
24 Correct 228 ms 84472 KB Output is correct
25 Correct 220 ms 83832 KB Output is correct
26 Correct 220 ms 83960 KB Output is correct
27 Correct 220 ms 83776 KB Output is correct
28 Correct 225 ms 83972 KB Output is correct
29 Correct 1356 ms 130340 KB Output is correct
30 Correct 1143 ms 120348 KB Output is correct
31 Correct 1146 ms 122200 KB Output is correct
32 Correct 1320 ms 130400 KB Output is correct
33 Correct 1447 ms 130292 KB Output is correct
34 Correct 1313 ms 128072 KB Output is correct
35 Correct 1314 ms 127676 KB Output is correct
36 Correct 1299 ms 127860 KB Output is correct
37 Correct 1307 ms 129272 KB Output is correct
38 Correct 944 ms 136184 KB Output is correct
39 Correct 943 ms 135928 KB Output is correct
40 Correct 945 ms 132728 KB Output is correct
41 Correct 907 ms 132112 KB Output is correct
42 Correct 914 ms 132216 KB Output is correct
43 Correct 924 ms 134076 KB Output is correct
44 Correct 1012 ms 135432 KB Output is correct
45 Correct 1018 ms 135460 KB Output is correct
46 Correct 1070 ms 132332 KB Output is correct
47 Correct 1022 ms 132012 KB Output is correct
48 Correct 994 ms 131832 KB Output is correct
49 Correct 995 ms 133988 KB Output is correct
50 Correct 1104 ms 133536 KB Output is correct
51 Correct 1105 ms 133452 KB Output is correct
52 Correct 1093 ms 131064 KB Output is correct
53 Correct 1143 ms 130728 KB Output is correct
54 Correct 1116 ms 130596 KB Output is correct
55 Correct 1114 ms 132376 KB Output is correct