Submission #602227

#	Time	Username	Problem	Language	Result	Execution time	Memory
602227		Tigryonochekk	Snowball (JOI21_ho_t2)	C++17	100 / 100	237 ms	13088 KiB

Main

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define pll pair<long long, long long>
const int N = 2e5 + 2;
const long long inf = 1e18 + 49;

int n, q;
long long x[N];
long long w[N];
vector<pll> v;
long long /*dif[N],*/ lef[N], rig[N];
long long ans[N];

int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	long long mx = 0, mn = 0;
	for (int i = 1; i <= q; i++) {
		cin >> w[i];
		w[i] += w[i - 1];
		mn = min(w[i], mn);
		mx = max(w[i], mn);
	}
	for (int i = 1; i < n; i++) {
		v.push_back(pll(x[i + 1] - x[i], i));
	}
	sort(v.begin(), v.end());
	int pnt = 0;
	long long cmx = 0, cmn = 0;
	for (int i = 1; i <= q; i++) {
		cmx = max(cmx, w[i]);
		cmn = min(cmn, w[i]);
		long long cur = cmx - cmn;
		while (pnt < v.size() && cur >= v[pnt].first) {
			long long dif = v[pnt].first;
			int ind = v[pnt].second;
			if (w[i] < 0) {
				lef[ind] = cmx;
				rig[ind] = dif - cmx;
			}
			else {
				rig[ind] = -cmn;
				lef[ind] = dif + cmn;
			}
			pnt++;
		}
	}
	for (; pnt < v.size(); pnt++) {
		int ind = v[pnt].second;
		lef[ind] = cmx;
		rig[ind] = -cmn;
	}
	ans[1] += -cmn;
	ans[n] += cmx;
	for (int i = 1; i < n; i++) {
		ans[i] += lef[i];
		ans[i + 1] += rig[i];
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   while (pnt < v.size() && cur >= v[pnt].first) {
      |          ~~~~^~~~~~~~~~
Main.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (; pnt < v.size(); pnt++) {
      |         ~~~~^~~~~~~~~~
Main.cpp:25:12: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   25 |  long long mx = 0, mn = 0;
      |            ^~

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