Submission #602346

#	Time	Username	Problem	Language	Result	Execution time	Memory
602346		CyberCow	Snowball (JOI21_ho_t2)	C++17	100 / 100	148 ms	14012 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
using namespace std;
using ll = long long;
vector<ll> v;
vector<pair<ll, pair<ll, ll>>> p;
ll ans[200005];

void solve()
{
	int n, i, j, q;
	cin >> n >> q;
	ll x, oo = 1000000000000000000LL;
	v.push_back(-oo);
	for ( i = 0; i < n; i++)
	{
		cin >> x;
		v.push_back(x);
	}
	v.push_back(oo);
	p.push_back({ 0,{ 0, 0 } });
	ll tex = 0;
	for ( i = 0; i < q; i++)
	{
		cin >> x;
		tex += x;
		pair<ll, pair<ll, ll>>anc = p.back();
		anc.second.first = max(anc.second.first, tex);
		anc.second.second = min(anc.second.second, tex);
		anc.first = anc.second.first - anc.second.second;
		p.push_back(anc);
	}
	sort(p.begin(), p.end());
	int ind;
	for (i = 1; i <= n; i++)
	{
		ind = lower_bound(p.begin(), p.end(), make_pair(v[i] - v[i - 1], make_pair(0LL, 0LL))) - p.begin();
		if (ind == p.size())
			ans[i] -= p[ind - 1].second.second;
		else
		{
			if (p[ind].second.second != p[ind - 1].second.second)
				ans[i] += v[i] - v[i - 1] - p[ind].second.first;
			else
				ans[i] += -p[ind].second.second;
		}
		ind = lower_bound(p.begin(), p.end(), make_pair(v[i + 1] - v[i], make_pair(0LL, 0LL))) - p.begin();
		if (ind == p.size())
			ans[i] += p[ind - 1].second.first;
		else
		{
			if (p[ind].second.first != p[ind - 1].second.first)
				ans[i] += v[i + 1] - v[i] - -p[ind].second.second;
			else
				ans[i] += p[ind].second.first;
		}
	}
	for ( i = 1; i <= n; i++)
	{
		cout << ans[i] << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:51:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   if (ind == p.size())
      |       ~~~~^~~~~~~~~~~
Main.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if (ind == p.size())
      |       ~~~~^~~~~~~~~~~
Main.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
   24 |  int n, i, j, q;
      |            ^

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