Submission #542622

#	Time	Username	Problem	Language	Result	Execution time	Memory
542622		jinhan814	Meteors (POI11_met)	C++17	0 / 100	1191 ms	27356 KiB

met

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

using ll = long long;

struct Query { int l, r, x; };

struct Fenwick {
	ll tree[300'001];
	void Init() { memset(tree, 0, sizeof tree); }
	void Update(int i, int val) {
		for (; i <= 300'000; i += i & -i) tree[i] += val;
	}
	ll Query(int i) {
		ll ret = 0;
		for (; i; i -= i & -i) ret += tree[i];
		return ret;
	}
} FT;

int n, m, q, v[300'001], lo[300'001], hi[300'001], I[300'001];
Query Q[300'001];
vector<int> pos[300'001];

void PBS() {
	iota(I + 1, I + n + 1, 1);
	for (int i = 1; i <= n; i++) lo[i] = 0, hi[i] = q + 1;
	while (1) {
		bool flag = 0;
		for (int i = 1; i <= n; i++) if (lo[i] + 1 < hi[i]) flag = 1;
		if (!flag) break;

		sort(I + 1, I + 1 + n, [&](int a, int b) {
			return lo[a] + hi[a] >> 1 < lo[b] + hi[b] >> 1;
		});
		FT.Init();

		for (int i = 1, j = 1; i <= q && j <= n; i++) {
			const auto& [l, r, x] = Q[i];
			if (l <= r) FT.Update(l, x), FT.Update(r + 1, -x);
			else FT.Update(l, x), FT.Update(1, x), FT.Update(r + 1, -x);
			for (; j <= n; j++) {
				if (lo[I[j]] + 1 == hi[I[j]]) continue;
				const int mid = lo[I[j]] + hi[I[j]] >> 1;
				if (mid > i) break;
				ll sum = 0;
				for (int i : pos[I[j]]) if ((sum += FT.Query(i)) >= v[I[j]]) break;
				if (sum < v[I[j]]) lo[I[j]] = mid;
				else hi[I[j]] = mid;
			}
		}
	}
}

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1, t; i <= m; i++) cin >> t, pos[t].push_back(i);
	for (int i = 1; i <= n; i++) cin >> v[i];
	cin >> q;
	for (int i = 1; i <= q; i++) cin >> Q[i].l >> Q[i].r >> Q[i].x;
	PBS();
	for (int i = 1; i <= q; i++) {
		if (hi[i] == q + 1) cout << "NIE" << '\n';
		else cout << hi[i] << '\n';
	}
}

Compilation message (stderr)

met.cpp: In lambda function:
met.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |    return lo[a] + hi[a] >> 1 < lo[b] + hi[b] >> 1;
      |           ~~~~~~^~~~~~~
met.cpp:35:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |    return lo[a] + hi[a] >> 1 < lo[b] + hi[b] >> 1;
      |                                ~~~~~~^~~~~~~
met.cpp: In function 'void PBS()':
met.cpp:45:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     const int mid = lo[I[j]] + hi[I[j]] >> 1;
      |                     ~~~~~~~~~^~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13