Submission #412998

#	Time	Username	Problem	Language	Result	Execution time	Memory
412998		joseacaz	Snowball (JOI21_ho_t2)	C++17	33 / 100	2589 ms	5648 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb push_back

const int MAXN = (int)2e5 + 5;
const ll INF = (1LL << 62LL);
int N, Q;
ll a[MAXN], spacesL[MAXN], spacesR[MAXN], W[MAXN];
ll l[MAXN], r[MAXN], pos;
ll finalL[MAXN], finalR[MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	for(int i = 1; i <= N; i++)
		cin >> a[i];
	a[0] = -INF, a[N + 1] = INF;
	for(int i = 0; i <= N + 1; i++)
	{
		if(i < N + 1)
			spacesR[i] = a[i + 1] - a[i];
		if(i > 0)
			spacesL[i] = a[i] - a[i - 1];
	}
	
	for(int q = 1; q <= Q; q++)
	{
		cin >> W[q];
		pos += W[q];
		l[q] = min(l[q - 1], pos);
		r[q] = max(r[q - 1], pos);
		
		if(l[q] < l[q - 1])
		{
			//cerr << l[q] << " " << r[q] << "\n";
			ll delta = l[q - 1] - l[q];
			for(int i = 1; i <= N + 1; i++)
			{
				if(spacesL[i] > 0 && spacesL[i] - delta <= 0)
					finalL[i] = a[i] + l[q - 1] - spacesL[i];
				spacesL[i] -= delta;
				//cerr << spacesL[i] << " ";
			}
			//cerr << "\n";

			for(int i = 0; i <= N; i++)
			{
				if(spacesR[i] > 0 && spacesR[i] - delta <= 0)
					finalR[i] = a[i] + r[q - 1];
				spacesR[i] -= delta;
				//cerr << spacesR[i] << " ";
			}
			//cerr << "INF\n";
		}
		else if(r[q] > r[q - 1])
		{
			ll delta = r[q] - r[q - 1];
			//cerr << l[q] << " " << r[q] << "\n";
			//cerr << "INF" << " ";
			for(int i = 1; i <= N + 1; i++)
			{
				if(spacesL[i] > 0 && spacesL[i] - delta <= 0)
					finalL[i] = a[i] + l[q - 1];
				spacesL[i] -= delta;
				//cerr << spacesL[i] << " ";
			}
			//cerr << "\n";

			for(int i = 0; i <= N; i++)
			{
				if(spacesR[i] > 0 && spacesR[i] - delta <= 0)
					finalR[i] = a[i] + r[q - 1] + spacesR[i];
				spacesR[i] -= delta;
				//cerr << spacesR[i] << " ";
			}
			//cerr << "INF\n";
		}
	}
	
	for(int i = 1; i <= N; i++)
	{
		if(spacesL[i] > 0)
			finalL[i] = a[i] + l[Q];
		if(spacesR[i] > 0)
			finalR[i] = a[i] + r[Q];
		
		//cerr << finalL[i] << " " << finalR[i] << "\n";
			
		cout << finalR[i] - finalL[i] << "\n";
	}
	
	return 0;
}

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