Submission #1033342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033342		juicy	Snowball (JOI21_ho_t2)	C++17	100 / 100	64 ms	14000 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

	const long long inf = 1e18;

	int N, Q; cin >> N >> Q;
	vector<long long> X = {-inf};
	for (int i = 0; i < N; ++i) {
		long long C; cin >> C;
		X.push_back(C);
	}
	X.push_back(inf);
	vector<long long> res(N + 2);
	vector<pair<long long, int>> cands;
	for (int i = 1; i <= N + 1; ++i) {
		cands.push_back({X[i] - X[i - 1], i});
	}
	auto solve = [&](pair<long long, int> x, long long a, long long b, long long A, long long B) {
		auto [len, id] = x;
		if (A + B <= len) {
			res[id - 1] += A;
			res[id] += B;
		} else {
			assert(a + b <= len);
			if (a != A) {
				res[id] += B;
				res[id - 1] += len - B;
			} else {
				res[id - 1] += A;
				res[id] += len - A;
			}
		}
	};
	sort(cands.begin(), cands.end());
	long long pf = 0, sf = 0, os = 0;
	int j = 0;
	while (Q--) {
		long long x; cin >> x;
		os += x;
		auto opf = pf, osf = sf;
		pf = max(pf, os);
		sf = max(sf, -os);
		while (j < cands.size() && cands[j].first <= pf + sf) {
			solve(cands[j++], opf, osf, pf, sf);
		}	
	}
	while (j < cands.size()) {
		solve(cands[j++], pf, sf, pf, sf);
	}
	for (int i = 1; i <= N; ++i) {
		cout << res[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   while (j < cands.size() && cands[j].first <= pf + sf) {
      |          ~~^~~~~~~~~~~~~~
Main.cpp:57:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  while (j < cands.size()) {
      |         ~~^~~~~~~~~~~~~~

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