oj.uz

Submission #969239

# Submission time Handle Problem Language Result Execution time Memory
969239 2024-04-24T18:24:10 Z duckindog Triple Jump (JOI19_jumps) C++17
0 / 100
 73 ms 25292 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);
      };
      
      int lt = j + 1, rt = (r + j) / 2 - 1;
      answer = max({answer, cal(lt), cal(rt + 1)});
      while (lt <= rt) { 
        int mid = lt + rt >> 1;
        if (cal(mid) <= cal(mid + 1)) { 
          answer = max(answer, cal(mid + 1));
          lt = mid + 1;
        } else rt = mid - 1;
      }
      
    }
    
    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]);
      |                                              ~~^~~
jumps.cpp: In function 'int32_t main()':
jumps.cpp:51:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = lt + rt >> 1;
      |                   ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 25292 KB Output isn't correct
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 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -