Submission #255236

#	Time	Username	Problem	Language	Result	Execution time	Memory
255236		islingr	Meteors (POI11_met)	C++14	100 / 100	1861 ms	42648 KiB

met

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)

using ll = int64_t;
const int N = 1 << 19;

int m; ll t[N << 1];
ll query(int p) {
	ll res = 0;
	for (p += m; p; p >>= 1) res += t[p];
	return res;
}

void upd(int l, int r, int a) {
	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if (l & 1) t[l++] += a;
		if (r & 1) t[--r] += a;
	}
}

void update(int l, int r, int a) {
	if (l < r) upd(l, r, a);
	else upd(l, m, a), upd(0, r, a);
}

int n, s[N], ans[N], a[N], b[N], c[N];
vector<int> q[N];

void solve(int l, int r, const vector<int> &cur) {
	if (r - l == 1 || cur.empty()) {
		for (int o : cur) ans[o] = l;
		return;
	}
	int m = (l + r) >> 1;
	rep(e, l, m) update(a[e], b[e], +c[e]);
	vector<int> L, R;
	for (int o : cur) {
		ll sum = 0;
		for (int z : q[o]) if (s[o] <= (sum += query(z))) break;
		if (s[o] <= sum) L.eb(o);
		else s[o] -= sum, R.eb(o);
	}
	rep(e, l, m) update(a[e], b[e], -c[e]);
	solve(l, m, L); solve(m, r, R);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	rep(i, 0, m) { int o; cin >> o; q[--o].eb(i); }
	rep(i, 0, n) cin >> s[i];
	int k; cin >> k;
	rep(i, 0, k) cin >> a[i] >> b[i] >> c[i], --a[i];
	vector<int> cur(n); iota(all(cur), 0);
	solve(0, k + 1, cur);
	rep(o, 0, n)
		if (ans[o] != k) cout << ans[o] + 1 << '\n';
		else cout << "NIE\n";
}

• 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