oj.uz

Submission #255236

# Submission time Handle Problem Language Result Execution time Memory
255236 2020-07-31T15:52:17 Z islingr Meteors (POI11_met) C++14
100 / 100
 1861 ms 42648 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12928 KB Output is correct
2 Correct 9 ms 12800 KB Output is correct
3 Correct 9 ms 12800 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12800 KB Output is correct
2 Correct 10 ms 12800 KB Output is correct
3 Correct 10 ms 12800 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15736 KB Output is correct
2 Correct 134 ms 17912 KB Output is correct
3 Correct 146 ms 16060 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 15864 KB Output is correct
2 Correct 154 ms 15972 KB Output is correct
3 Correct 92 ms 17484 KB Output is correct
4 Correct 36 ms 15224 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15480 KB Output is correct
2 Correct 92 ms 17528 KB Output is correct
3 Correct 42 ms 13952 KB Output is correct
4 Correct 146 ms 16248 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15352 KB Output is correct
2 Correct 139 ms 16120 KB Output is correct
3 Correct 93 ms 15480 KB Output is correct
4 Correct 182 ms 17144 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 38652 KB Output is correct
2 Correct 197 ms 27820 KB Output is correct
3 Correct 233 ms 18040 KB Output is correct
4 Correct 1861 ms 39532 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 36632 KB Output is correct
2 Correct 257 ms 27508 KB Output is correct
3 Correct 107 ms 18552 KB Output is correct
4 Correct 1741 ms 42648 KB Output is correct