Submission #512822

#	Time	Username	Problem	Language	Result	Execution time	Memory
512822		jesus_coconut	Snowball (JOI21_ho_t2)	C++17	100 / 100	121 ms	21572 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a), end(a)
#define F first
#define S second
using namespace std;

using ll = long long;



vector<ll> v, Q;
void load() {
  int n, q;
  cin >> n >> q;
  v.resize(n);
  Q.resize(q);
  for (auto &it : v) cin >> it;
  for (auto &it: Q) cin >> it;
}


void fix(vector<ll> const &a, vector<ll> const &b, vector<pair<ll, int>> const &items, vector<ll> &ans) {
  int p = (int)size(a) - 1;
  for (auto const &[len, idx] : items) {
	while (p >= 0 && a[p] + b[p] > len) --p;
	ll add = 0;
	if (p != size(a) - 1) add = max(add, len - b[p + 1]);
	if (p != -1) add = max(add, a[p]);
	ans[idx] += add;
  }
}

void solve() {
  Q.insert(begin(Q), 0);
  partial_sum(begin(Q), end(Q), begin(Q));
  vector<ll> mxs(size(Q)), mns(size(Q));
  partial_sum(begin(Q), end(Q), begin(mxs), [](ll a, ll b) {
	return max(a, b);
  });
  partial_sum(begin(Q), end(Q), begin(mns), [](ll a, ll b) {
	return max(a, -b);
  });
  vector<ll> ans(size(v));
  vector<pair<ll, int>> rs(size(v) - 1), ls(size(v) - 1);
  ans[0] += mns.back();
  ans.back() += mxs.back();
  for (int i = 0; i < size(v); ++i) {
	if (i != 0) ls[i - 1] = {v[i] - v[i - 1], i};
	if (i != size(v) - 1) rs[i] = {v[i+1] - v[i], i};
  }
  sort(all(rs), greater<>());
  sort(all(ls), greater<>());
  fix(mxs, mns, rs, ans);
  fix(mns, mxs, ls, ans);
  for (auto it: ans) {
	cout << it << '\n';
  }
}

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


  load();
  solve();

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void fix(const std::vector<long long int>&, const std::vector<long long int>&, const std::vector<std::pair<long long int, int> >&, std::vector<long long int>&)':
Main.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if (p != size(a) - 1) add = max(add, len - b[p + 1]);
      |      ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < size(v); ++i) {
      |                   ~~^~~~~~~~~
Main.cpp:51:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  if (i != size(v) - 1) rs[i] = {v[i+1] - v[i], i};
      |      ~~^~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67