oj.uz

Submission #197612

# Submission time Handle Problem Language Result Execution time Memory
197612 2020-01-22T02:30:50 Z sinhriv Triple Jump (JOI19_jumps) C++17
27 / 100
 178 ms 25328 KB 
/***
Todo:

If we fix A, then B should be the next element to the right which is > A
Same thing happens if we fix B.

So stack to find the closest greater left and right.

After that do something with C?
***/


#include<bits/stdc++.h>
#define left owo
#define right uwu

using namespace std;

const int N = 4002000;
const int MAXN = 500050;

struct SegmentTree{
  int ans[N];
  int best[N];
  int lazy[N];

  #define mid ((l + r) >> 1)

  void push(int x) {
    ans[x] = max(ans[x], best[x] + lazy[x]);
    lazy[x << 1] = max(lazy[x << 1], lazy[x]);
    lazy[x << 1 | 1] = max(lazy[x << 1 | 1], lazy[x]);
    lazy[x] = 0;
    return;
  }

  void modify(int x, int l, int r, int pos, int val) {
    push(x);
    if(l == r) {
      best[x] = max(best[x], val);
      return;
    }
    if(pos <= mid) modify(x << 1, l, mid, pos, val);
    else modify(x << 1 | 1, mid + 1, r, pos, val);
    best[x] = max({best[x], best[x << 1], best[x << 1 | 1]});
    return;
  }

  int query(int x, int l, int r, int pos) {
    push(x);
    if(r < pos) return -1;
    if(l >= pos) return ans[x];
    int ret = max(query(x << 1, l, mid, pos), query(x << 1 | 1, mid + 1, r, pos));
    ans[x] = max({ans[x], ans[x << 1], ans[x << 1 | 1]});
    return ret;
  }
  #undef mid
}seg;

int n, q;
int a[MAXN];
int left[MAXN];
int right[MAXN];
int answer[MAXN];
vector<pair<int, int>> queries[MAXN];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);

  cin >> n;
  for(int i = 0; i < n; ++i) cin >> a[i];

  vector<int> st;
  for(int i = 0; i < n; ++i) {
    while(!st.empty() && a[i] >= a[st.back()]) {
      right[st.back()] = i;
      st.pop_back();
    }
    if(!st.empty()) left[i] = st.back();
    else left[i] = -1;
    st.push_back(i);
  }

  while(!st.empty()) {
    right[st.back()] = -1;
    st.pop_back();
  }

  cin >> q;
  for(int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    queries[--r].emplace_back(--l, i);
  }

  set<pair<int, int>> que;
  for(int i = 0; i < n; ++i) {
    if(right[i] != -1) {
      que.emplace(2 * right[i] - i, i);
    }
    if(left[i] != -1) {
      que.emplace(2 * i - left[i], i + MAXN);
    }

    while(!que.empty() && que.begin() -> first <= i) {
      auto p = *que.begin(); que.erase(que.begin());
      int x, y;
      if(p.second >= MAXN) {
        p.second -= MAXN;
        x = left[p.second];
        y = p.second;
      }
      else {
        x = p.second;
        y = right[p.second];
      }
      seg.modify(1, 0, n - 1, x, a[x] + a[y]);
    }

    /// update on IT as C = a[i]
    seg.lazy[1] = max(seg.lazy[1], a[i]);
    /// answer for queries
    for(auto q : queries[i]) {
      answer[q.second] = seg.query(1, 0, n - 1, q.first);
    }
  }

  for(int i = 0; i < q; ++i) {
    cout << answer[i] << "\n";
  }

  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Incorrect 16 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Incorrect 16 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 24368 KB Output is correct
2 Correct 97 ms 24440 KB Output is correct
3 Correct 95 ms 25328 KB Output is correct
4 Correct 172 ms 24516 KB Output is correct
5 Correct 167 ms 24440 KB Output is correct
6 Correct 178 ms 23844 KB Output is correct
7 Correct 170 ms 23800 KB Output is correct
8 Correct 172 ms 23712 KB Output is correct
9 Correct 173 ms 24104 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Incorrect 16 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -