Submission #781122

#	Time	Username	Problem	Language	Result	Execution time	Memory
781122		arnold518	Rainy Markets (CCO22_day1problem2)	C++17	25 / 25	670 ms	147088 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll INF = 1e18;

int N;
ll A[MAXN+10], B[MAXN+10], P[MAXN+10], PP[MAXN+10];
pll ans[MAXN+10];
ll ans2[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	void update(int i, ll k) { for(; i<=N; i+=(i&-i)) tree[i]+=k; }
	ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
	for(int i=1; i<N; i++) scanf("%lld", &P[i]), PP[i]=P[i];
	for(int i=1; i<N; i++) scanf("%lld", &B[i]);

	for(int i=1; i<N; i++)
	{
		ll t=min(P[i], A[i]);
		P[i]-=t; A[i]-=t; ans[i].first=t;

		t=min(P[i], A[i+1]);
		P[i]-=t; A[i+1]-=t; ans[i].second=t;
	}

	vector<pll> VL, VR;
	for(int i=N-1; i>=2; i--) VR.push_back({ans[i].first, i});
	for(int i=1; i<N; i++)
	{
		ll t=min(P[i], B[i]);
		P[i]-=t; B[i]-=t;

		while(!VL.empty() && P[i])
		{
			t=min({P[i], VL.back().first, B[VL.back().second]});
			P[i]-=t; VL.back().first-=t; B[VL.back().second]-=t;
			bit.update(i, t); bit.update(VL.back().second, -t);

			if(VL.back().first==0) VL.clear();
			else if(B[VL.back().second]==0)
			{
				pll tt=VL.back(); VL.pop_back();
				if(!VL.empty()) VL.back().first=min(VL.back().first, tt.first);
			}
		}

		while(!VR.empty() && VR.back().second<=i) VR.pop_back();
		while(!VR.empty() && P[i])
		{
			t=min({P[i], VR.back().first, B[VR.back().second]});
			P[i]-=t; VR.back().first-=t; B[VR.back().second]-=t;
			bit.update(i, t); bit.update(VR.back().second, -t);

			if(VR.back().first==0) break;
			else if(B[VR.back().second]==0)
			{
				pll tt=VR.back(); VR.pop_back();
				if(!VR.empty()) VR.back().first=min(VR.back().first, tt.first);
			}
		}

		if(P[i]) return !printf("NO\n");

		VL.push_back({bit.query(i)+ans[i].second, i});
	}
	for(int i=1; i<N; i++)
	{
		ll t=bit.query(i);
		ans[i].second+=t, ans[i+1].first-=t;
	}

	ll sum=0;
	for(int i=1; i<N; i++)
	{
		ans2[i]=PP[i]-ans[i].first-ans[i].second;
		sum+=ans2[i];
	}
	printf("YES\n%lld\n", sum);
	for(int i=1; i<N; i++) printf("%lld %lld %lld\n", ans[i].first, ans2[i], ans[i].second);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
Main.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  for(int i=1; i<N; i++) scanf("%lld", &P[i]), PP[i]=P[i];
      |                         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:28:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  for(int i=1; i<N; i++) scanf("%lld", &B[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9