Submission #1307446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307446		repmann	Triple Jump (JOI19_jumps)	C++20	100 / 100	863 ms	65264 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, K, Q;
int A[500001];
struct Query
{
  int l, r, i;
  const bool operator < (const Query &q) const {return l < q.l;}
}QR[500001];
struct Node
{
  ll max0, max1, mind, maxd, p;
}ST[2000001];
vector <pair <int, int>> V;
ll O[500001];
inline void Merge(int i)
{
  if(i >= K) return;
  ST[i].mind = min(ST[i << 1].mind, ST[i << 1 | 1].mind);
  ST[i].maxd = max(ST[i << 1].maxd, ST[i << 1 | 1].maxd);
  ST[i].max1 = max(ST[i << 1].max1, ST[i << 1 | 1].max1);
  return;
}
inline void Propagate(int i)
{
  if(!ST[i].p) return;
  ST[i].max1 = ST[i].max0 + (ST[i].mind = ST[i].maxd = ST[i].p);
  if(i < K) ST[i << 1].p = ST[i << 1 | 1].p = ST[i].p;
  ST[i].p = 0;
  return;
}
inline void Setup()
{
  K = 1;
  while(K < N) K <<= 1;
  for(int i = 1; i <= N; i++) ST[i + K - 1] = {A[i], 0, 0, 0, 0};
  for(int i = K - 1; i; i--) ST[i].max0 = max(ST[i << 1].max0, ST[i << 1 | 1].max0);
  for(int i = K - 1; i; i--) Merge(i);
  return;
}
inline void Update(int l, int r, ll x, int i = 1, int lc = 1, int rc = K)
{
  Propagate(i);
  if((lc > r) || (l > rc)) return;
  if((l <= lc) && (rc <= r) && (ST[i].mind >= x)) return;
  if((l <= lc) && (rc <= r) && (ST[i].mind == ST[i].maxd)) {ST[i].p = x; return Propagate(i);}
  int s = (lc + rc) >> 1;
  Update(l, r, x, i << 1, lc, s);
  Update(l, r, x, i << 1 | 1, s + 1, rc);
  Merge(i);
  return;
}
inline ll Get(int l, int r, int i = 1, int lc = 1, int rc = K)
{
  Propagate(i);
  if((lc > r) || (l > rc)) return 0;
  if((l <= lc) && (rc <= r)) return ST[i].max1;
  int s = (lc + rc) >> 1;
  ll ret = max(Get(l, r, i << 1, lc, s), Get(l, r, i << 1 | 1, s + 1, rc));
  Merge(i);
  return ret;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N;
  for(int i = 1; i <= N; i++) cin >> A[i];
  Setup();
  stack <pair <int, int>> S;
  for(int i = 1; i <= N; i++)
  {
    while(S.size() && (S.top().first < A[i])) S.pop();
    if(S.size()) V.push_back({S.top().second, i});
    S.push({A[i], i});
  }
  while(S.size()) S.pop();
  for(int i = N; i >= 1; i--)
  {
    while(S.size() && (S.top().first < A[i])) S.pop();
    if(S.size()) V.push_back({i, S.top().second});
    S.push({A[i], i});
  }
  sort(V.begin(), V.end());
  cin >> Q;
  for(int i = 1; i <= Q; i++) {cin >> QR[i].l >> QR[i].r; QR[i].i = i;}
  sort(QR + 1, QR + Q + 1);
  for(int i = Q, j = V.size() - 1, l = N + 1; i >= 1; i--)
  {
    while((j >= 0) && (V[j].first >= QR[i].l))
    {
      if(((V[j].second << 1) - V[j].first) <= N)
      {
        Update((V[j].second << 1) - V[j].first, N, A[V[j].first] + A[V[j].second]);
        l = min((V[j].second << 1) - V[j].first, l);
      }
      j--;
    }
    O[QR[i].i] = Get(max(l, QR[i].l), QR[i].r);
  }
  for(int i = 1; i <= Q; i++) cout << O[i] << " \n"[i == Q];

  return 0;
}

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