Submission #1213980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213980		k1r1t0	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	28 / 100	4094 ms	29016 KiB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 251000;
const int Q = 51000;

int n, q, l[N], a[N], dp[N];
vector<array<int, 2>> vec[N];

int solve() {
	for (int i = 1; i <= n + 1; i++)
		vec[i].clear();
	for (int i = 1; i <= n + 1; i++)
		a[i] += a[i - 1];
	for (int i = 1; i <= n + 1; i++)
		dp[i] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
		if (a[i - 1] > a[i] - a[i - 1])
			dp[i] = 2;
	multiset<pair<int, int>> st;
	for (int i = 1; i <= n + 1; i++) {
		//a[i] < 2 * a[j - 1] - a[j]
		for (auto [k, v] : vec[i]) {
			auto it = st.lower_bound({k, v});
			if (it != st.begin()) {
				it--;
				if (it->second >= v)
					continue;
			}
			while (true) {
				it = st.lower_bound({k, v});
				if (it == st.end()) break;
				if (it->second <= v) {
					st.erase(it);
					continue;
				}
				break;
			}
			st.insert({k, v});
		}
		auto it = st.lower_bound(pair<int, int>{2 * a[i - 1] - a[i], -1ll});
		if (it != st.begin()) {
			it--;
			dp[i] = max(dp[i], it->second);
		}
		// 2 * a[i] - a[i - 1] < a[j - 1]
		int l = i + 2, r = n + 2, val = 2 * a[i] - a[i - 1];
		while (l < r) {
			int mid = (l + r) / 2;
			if (val < a[mid - 1]) r = mid;
			else l = mid + 1;
		}
		if (l <= n + 1) vec[l].push_back({a[i], dp[i] + 2});
	}
	return max({dp[n + 1] - 1, dp[n], 1ll});
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> l[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int x, y, aa, bb; cin >> x >> y >> aa >> bb; aa++;
		l[x] = y;
		for (int i = 1; i <= bb - aa + 1; i++)
			a[i] = l[i + aa - 1];
		n = bb - aa + 1;
		a[n + 1] = 0;
		cout << solve() << '\n';
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11