Submission #870399

#	Time	Username	Problem	Language	Result	Execution time	Memory
870399		aaron_dcoder	Snowball (JOI21_ho_t2)	C++17	100 / 100	223 ms	14408 KiB

Main

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;

struct snowscape {
	ll lsnowgone;
	ll rsnowgone;

	bool operator <(ll oth) const {
		return (lsnowgone+rsnowgone) < oth;
	}

	bool operator !=(const snowscape& oth) const {
		return pll{lsnowgone,rsnowgone} != pll{oth.lsnowgone,oth.rsnowgone};
	}


};

int main() {
	ll N,Q;
	cin >> N >> Q;

	vector<ll> X(N);
	vector<ll> W(Q);

	for (ll i = 0; i < N; ++i)
	{
		cin >> X[i];
	}
	for (ll i = 0; i < Q; ++i)
	{
		cin >> W[i];
	}

    snowscape curr = {0,0};
	vector<snowscape> landmarks = {curr,};
	ll cpos=0;
	for (ll wi : W)
	{
		cpos+=wi;
		curr.lsnowgone = max(curr.lsnowgone,cpos);
		curr.rsnowgone = max(curr.rsnowgone,-cpos);
		if (curr!=*landmarks.crbegin()) landmarks.push_back(curr);
	}

	vector<ll> outp(N);
	outp[0]+=landmarks.crbegin()->rsnowgone;
	outp[N-1]+=landmarks.crbegin()->lsnowgone;
	dbgv(landmarks.crbegin()->rsnowgone);
	for (ll i = 0; i < N-1; ++i)
	{
		auto lit = lower_bound(landmarks.cbegin(),landmarks.cend(),X[i+1]-X[i]);
		auto jb = lit-1;
		if (lit==landmarks.cend()) {
			outp[i] += jb->lsnowgone;
			outp[i+1] += jb->rsnowgone;
		}
		else {
			if (lit->lsnowgone > jb->lsnowgone) {
				outp[i] += (X[i+1]-X[i]) - jb->rsnowgone;
				outp[i+1] += jb->rsnowgone;
			}
			else {
				outp[i] += jb->lsnowgone;
				outp[i+1] +=  (X[i+1]-X[i]) - jb->lsnowgone;
			}
		}
	}

	for (ll o : outp)
	{
		cout << o << "\n";
	}




}

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