oj.uz

Submission #969240

# Submission time Handle Problem Language Result Execution time Memory
969240 2024-04-24T18:29:13 Z duckindog Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 23528 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Execution timed out 4010 ms 14676 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 23528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Execution timed out 4010 ms 14676 KB Time limit exceeded
12 Halted 0 ms 0 KB -