Submission #1023839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023839		avighna	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	791 ms	232264 KiB

SolarStorm

#include <bits/stdc++.h>

typedef long long ll;

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

const ll N = 1e6 + 1;

ll d[N], v[N], pd[N], pv[N], left[N], right[N];
ll lift[N][20];

int main() {
  ll n, s, k;
  std::cin >> n >> s >> k;
  for (ll i = 2; i <= n; ++i) {
    std::cin >> d[i];
  }
  for (ll i = 1; i <= n; ++i) {
    std::cin >> v[i];
  }
  std::partial_sum(d, d + n + 1, pd);
  std::partial_sum(v, v + n + 1, pv);
  
  // for (ll i = 0; i <= n; ++i) std::cout << pd[i] << ' ';
  // std::cout << std::endl;
  
  for (ll i = 1; i <= n; ++i) {
    left[i] = BinarySearchMin(1, i, [&](ll m) {
      return pd[i] - pd[m] <= k;
    });
    right[i] = BinarySearchMax(i, n, [&](ll m) {
      return pd[m] - pd[i] <= k;
    });
    // std::cout << i << " -> " << std::min(n, right[i] + 1) << std::endl;
  }
  for (ll i = 1; i <= n; ++i) {
    lift[i][0] = BinarySearchMax(i, n, [&](ll m) {
      return left[m] - right[i] <= 1;
    });
  }
  for (int bt = 1; bt < 20; ++bt) {
    for (ll i = 1; i <= n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];;
    }
  }
  
  std::pair<ll, ll> best;
  for (ll i = 1; i <= n; ++i) {
    ll j = i;
    for (int bt = 0; bt < 20; ++bt) {
      if ((s - 1) & (1 << bt)) {
        j = lift[j][bt];
      }
    }
    // std::cout << "i="<<left[i]<<",j="<<right[j]<<std::endl;
    best = std::max(best, std::make_pair(pv[right[j]] - pv[left[i] - 1], i));
  }
  
  std::vector<ll> ans;
  for (ll i = 0, v = best.second; i < s; ++i) {
    ans.push_back(v);
    v = lift[v][0];
  }
  while (ans.size() >= 2 and ans[ans.size() - 1] == ans[ans.size() - 2]) {
    ans.pop_back();
  }
  std::cout << ans.size() << '\n';
  for (auto &i : ans) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

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