Submission #1023483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023483		avighna	Solar Storm (NOI20_solarstorm)	C++17	8 / 100	537 ms	163528 KiB

SolarStorm

#include <bits/stdc++.h>

typedef long long ll;

ll BinarySearchMax(ll s, ll e, const std::function<bool(ll)> &f) {
  ll ans = s;
  while (s <= e) {
    ll m = s + (e - s) / 2;
    if (f(m)) {
      ans = m;
      s = m + 1;
    } else {
      e = m - 1;
    }
  }
  return ans;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, s;
  ll k;
  std::cin >> n >> s >> k;
  std::vector<ll> d(n - 1);
  for (auto &i : d) {
    std::cin >> i;
  }
  std::vector<ll> dsum(n - 1);
  std::partial_sum(d.begin(), d.end(), dsum.begin());
  std::vector<ll> v(n);
  for (auto &i : v) {
    std::cin >> i;
  }

  std::vector<std::vector<int>> lift(n, std::vector<int>(21));
  // ll dist = 0;
  // for (int i = n - 1, j = n - 1; i >= 0; --i) {
  //   if (i != n - 1) {
  //     dist += d[i];
  //   }
  //   // j is the last index satisfying dist[i...j] <= k
  //   while (dist > k and j - 1 >= 0) {
  //     dist -= d[j - 1];
  //     j--;
  //   }
  //   lift[i][0] = std::min(n - 1, j + 1);
  // }
  for (int i = 0; i < n; ++i) {
    int j = BinarySearchMax(i, n - 1, [&](ll m) {
      ll cur = 0;
      if (m - 1 >= 0) {
        cur += dsum[m - 1];
      }
      if (i - 1 >= 0) {
        cur -= dsum[i - 1];
      }
      return cur <= k;
    });
    lift[i][0] = std::min(n - 1, j + 1);
  }
  for (int bt = 1; bt <= 20; ++bt) {
    for (int i = 0; i < n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
    }
  }

  auto binary_lift = [&](ll node, ll k) {
    for (ll bt = 0; bt <= 20; ++bt) {
      if (k & (1 << bt)) {
        node = lift[node][bt];
      }
    }
    return node;
  };

  std::vector<ll> psum(n);
  std::partial_sum(v.begin(), v.end(), psum.begin());
  auto sum = [&](int l, int r) {
    ll ans = psum[r];
    if (l - 1 >= 0) {
      ans -= psum[l - 1];
    }
    return ans;
  };

  std::pair<ll, int> best;
  for (int i = 0; i < n; ++i) {
    best = std::max(best, std::make_pair(sum(i, binary_lift(i, s - 1)), i));
  }

  std::vector<int> ans;
  for (int i = 0, node = best.second; i < s; ++i) {
    ans.push_back(node);
    node = lift[node][0];
  }
  while (ans.size() >= 2 and ans.back() == ans[ans.size() - 2]) {
    ans.pop_back();
  }
  std::cout << ans.size() << "\n";
  for (auto &i : ans) {
    std::cout << i + 1 << " ";
  }
  std::cout << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30