Submission #886427

#	Time	Username	Problem	Language	Result	Execution time	Memory
886427		tsumondai	Rainy Markets (CCO22_day1problem2)	C++14	25 / 25	516 ms	152496 KiB

Main

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

#define Task "problemname"
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int MAXN = 1e6 + 5;

const int oo = 1e18, mod = 1e9 + 7;

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

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

void process() {
	cin >> N;
	foru(i,1,N) cin >> A[i];
	foru(i,1,N-1) cin >> P[i], PP[i] = P[i];
	foru(i,1,N-1) cin >> B[i];

	foru(i,1,N-1) {
		int 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<ii> VL, VR;
	for (int i = N - 1; i >= 2; i--) VR.push_back({ans[i].first, i});
	foru(i,1,N-1) {
		int 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) {
				ii 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) {
				ii tt = VR.back(); VR.pop_back();
				if (!VR.empty()) VR.back().first = min(VR.back().first, tt.first);
			}
		}

		if (P[i]) {
			cout << "NO\n"; return;
		}

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

	int sum = 0;
	foru(i,1,N-1) {
		ans2[i] = PP[i] - ans[i].first - ans[i].second;
		sum += ans2[i];
	}
	cout << "YES\n" << sum << '\n';
	foru(i, 1, N - 1) cout << ans[i].fi << ' ' << ans2[i] << ' ' << ans[i].se << '\n';
	cout << '\n';
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	if (fopen(Task".INP", "r")) {
		freopen(Task".INP", "r", stdin);
		freopen(Task".OUT", "w", stdout);
	}
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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