Submission #1125526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125526		dynam1c	Stranded Far From Home (BOI22_island)	C++20	15 / 100	230 ms	19396 KiB

island

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int L = 21;
struct Sparse {
  int n;
  vector<array<int, L>> seg;
  Sparse(const vector<int>& arr) : n(arr.size()), seg(arr.size()+1) {
    for (int i = 0; i < n; i++)
      seg[i][0] = arr[i];
    for (int l = 1; l < L; l++)
      for (int i = 0; i+(1<<l) <= n; i++)
        seg[i][l] = max(seg[i][l-1], seg[i+(1<<(l-1))][l-1]);
  }
  int find_right(int i, ll x) {
    for (int l = L-1; l >= 0; l--)
      if (i + (1<<l) <= n && seg[i][l] <= x)
        i += (1<<l);
    return i;
  }
  int find_left(int i, ll x) {
    for (int l = L-1; l >= 0; l--)
      if (i - (1<<l) >= 0 && seg[i-(1<<l)][l] <= x)
        i -= (1<<l);
    return i;
  }
};
int main() {
  int n, m, _;
  cin >> n >> m;
  vector<int> arr(n);
  for (int& e : arr)
    cin >> e;
  Sparse st(arr);
  while (m--)
    cin >> _ >> _;

  vector<ll> pref(n+1);
  for (int i = 0; i < n; i++)
    pref[i+1] = pref[i] + arr[i];

  for (int i = 0; i < n; i++) {
    int l = i, r = i+1;
    while (true) {
      ll s = pref[r] - pref[l];
      int nr = st.find_right(r, s), nl = st.find_left(l, s);
      if (nl == l && nr == r)
        break;
      l = nl, r = nr;
    }
    cout << (l == 0 && r == n ? "1" : "0");
  }
  cout << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35