Submission #197615

#	Time	Username	Problem	Language	Result	Execution time	Memory
197615		sinhriv	Triple Jump (JOI19_jumps)	C++17	100 / 100	1232 ms	91200 KiB

jumps

/***
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)

  SegmentTree() {
    for(int i = 0; i < N; ++i) ans[i] = best[i] = (int)-1e9;
  }

  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]});
    ans[x] = max({ans[x], ans[x << 1], ans[x << 1 | 1]});
    return;
  }

  int query(int x, int l, int r, int pos) {
    push(x);
    if(r < pos) return -1;
    if(l >= pos){
      //cout << l << " " << r << " " << ans[x] << endl;
      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;
  //b - a <= c - b -> 2b - a <= c
  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";
  }

  // chiu cha biet sai gi


  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54