Submission #197703

#	Time	Username	Problem	Language	Result	Execution time	Memory
197703		quocnguyen1012	Triple Jump (JOI19_jumps)	C++14	100 / 100	1357 ms	104568 KiB

jumps

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 5;
const ll inf = 1e17;

class node
{
public:
  ll mx, mx_arr, ret;
  node(ll mx = 0, ll mx_arr = 0, ll ret = 0):
    mx(mx), mx_arr(mx_arr), ret(ret) {}
  node operator + (const node & other) const
  {
    node res;
    res.ret = max({ret, other.ret, mx_arr + other.mx});
    res.mx = max(mx, other.mx);
    res.mx_arr = max(mx_arr, other.mx_arr);
    return res;
  }
};

class segment_tree
{
  vector<node> ST;
public:
  segment_tree(int n)
  {
    ST.assign(4 * n + 5, node(-inf, -inf, -inf));
  }
#define lc id << 1
#define rc id << 1 | 1
  void update(int id, int l, int r, int pos, ll val, bool need)
  {
    if (l > pos || r < pos) return;
    if (l == r){
      if (need) ST[id].mx = max(ST[id].mx, val);
      else ST[id].mx_arr = max(ST[id].mx_arr, val);
      ST[id].ret = max(-inf, ST[id].mx + ST[id].mx_arr);
      return;
    }
    int mid = (l + r) / 2;
    update(lc, l, mid, pos, val, need); update(rc, mid + 1, r, pos, val, need);
    ST[id] = ST[lc] + ST[rc];
  }
  node sum(int id, int l, int r, int L, int R)
  {
    if (L > R || l > R || L > r) return node(-inf, -inf, -inf);
    if (L <= l && r <= R) return ST[id];
    int mid = (l + r) / 2;
    return sum(lc, l, mid, L, R) + sum(rc, mid + 1, r, L, R);
  }
#undef lc
#undef rc
};

int N, Q;
int a[maxn];
vector<pair<int, int>> query[maxn];
ll res[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  vector<int> st;
  vector<pair<int, int>> good;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    while (st.size() && a[i] >= a[st.back()]){
      good.pb(mp(st.back(), i));
      st.pop_back();
    }
    if (st.size())
      good.pb(mp(st.back(), i));
    st.pb(i);
  }
  sort(good.rbegin(), good.rend());
  ///for (auto & all : good) cerr << all.fi << ' ' << all.se << '\n';
  cin >> Q;
  for (int i = 1; i <= Q; ++i){
    int l, r; cin >> l >> r;
    query[l].pb(mp(r, i));
  }
  segment_tree tree(N);
  int j = 0;
  for (int i = N; i >= 1; --i){
    tree.update(1, 1, N, i, a[i], true);
    while (j < (int)good.size() && good[j].fi >= i){
      int pos = 2 * good[j].se - good[j].fi;
      ll val = a[good[j].fi] + a[good[j].se];
      if (pos <= N) tree.update(1, 1, N, pos, val, false);
      ++j;
    }
    for (auto & all : query[i]){
      res[all.se] = tree.sum(1, 1, N, i, all.fi).ret;
    }
  }
  for (int i = 1; i <= Q; ++i){
    cout << res[i] << '\n';
  }
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jumps.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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