Submission #969240

#	Time	Username	Problem	Language	Result	Execution time	Memory
969240		duckindog	Triple Jump (JOI19_jumps)	C++17	5 / 100	4038 ms	23528 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int N = 500'000 + 10;
int n;
int a[N];
int q;
struct Query {
  int l, r;
  friend istream& operator >> (istream& is, auto& rhs) {
    return is >> rhs.l >> rhs.r;
  }
} Q[N];

int f[N][19], lg[N];
void deal() { 
  for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
  for (int i = 1; i <= n; ++i) f[i][0] = a[i];

  for (int j = 1; j <= 18; ++j) 
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) 
      f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int get(int l, int r) { 
  int j = lg[r - l + 1];
  return max(f[l][j], f[r - (1 << j) + 1][j]);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  cin >> q;
  for (int i = 1; i <= q; ++i) cin >> Q[i];

  deal();

  for (int i = 1; i <= q; ++i) { 
    const auto& [l, r] = Q[i];
    long long answer = 0;
    for (int j = l; j <= r - 2; ++j) { 
      auto cal = [&](int mid) { 
        return 1ll * a[j] + get(j + 1, mid) + get(mid + mid - j, r);
      };
      for (int t = j + 1; t <= (j + r) / 2; ++t) answer = max(answer, cal(t));
    }
    
    cout << answer << "\n";
  }

}

Compilation message (stderr)

jumps.cpp:11:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   11 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~
jumps.cpp: In function 'void deal()':
jumps.cpp:23:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |       f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
      |                                              ~~^~~

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