Submission #226647

#	Time	Username	Problem	Language	Result	Execution time	Memory
226647		dolphingarlic	Meteors (POI11_met)	C++14	100 / 100	2021 ms	61288 KiB

met

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, l[300002], r[300002];
ll bit[300002], req[300002], num[300002];
pair<int, int> event[300002];
vector<int> owned[300002], to_check[300002];

void update(int pos, ll val) {
	for (; pos <= m; pos += (pos & (-pos))) bit[pos] += val;
}

ll query(int pos) {
	ll ans = 0;
	for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
	return ans;
}

void update(pair<int, int> range, ll val) {
	if (range.first > range.second) update(1, val);
	update(range.first, val), update(range.second + 1, -val);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	FOR(i, 1, m + 1) {
		int x;
		cin >> x;
		owned[x].push_back(i);
	}
	FOR(i, 1, n + 1) cin >> req[i];

	int k;
	cin >> k;
	FOR(i, 1, k + 1) cin >> event[i].first >> event[i].second >> num[i];

	FOR(i, 1, n + 1) l[i] = 1, r[i] = k + 1;
	bool done = false;
	while (!done) {
		done = true;

		fill(bit + 1, bit + m + 1, 0);
		FOR(i, 1, n + 1) if (l[i] != r[i]) to_check[(l[i] + r[i]) / 2].push_back(i);

		FOR(i, 1, k + 1) {
			update(event[i], num[i]);
			while (to_check[i].size()) {
				done = false;
				int nation = to_check[i].back();
				to_check[i].pop_back();

				ll tot = 0;
				for (int j : owned[nation]) {
					tot += query(j);
					if (tot >= req[nation]) break;
				}
				if (tot >= req[nation]) r[nation] = i;
				else l[nation] = i + 1;
			}
		}
	}

	FOR(i, 1, n + 1) {
		if (l[i] == k + 1) cout << "NIE\n";
		else cout << l[i] << '\n';
	}
	return 0;
}

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