oj.uz

Submission #226647

# Submission time Handle Problem Language Result Execution time Memory
226647 2020-04-24T16:47:01 Z dolphingarlic Meteors (POI11_met) C++14
100 / 100
 2021 ms 61288 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14592 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Correct 13 ms 14592 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16504 KB Output is correct
2 Correct 120 ms 18552 KB Output is correct
3 Correct 113 ms 18048 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 17528 KB Output is correct
2 Correct 113 ms 17656 KB Output is correct
3 Correct 120 ms 18680 KB Output is correct
4 Correct 41 ms 16760 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 16888 KB Output is correct
2 Correct 107 ms 19064 KB Output is correct
3 Correct 58 ms 15352 KB Output is correct
4 Correct 109 ms 18552 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 15992 KB Output is correct
2 Correct 111 ms 17528 KB Output is correct
3 Correct 84 ms 16248 KB Output is correct
4 Correct 136 ms 19868 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 35552 KB Output is correct
2 Correct 686 ms 22864 KB Output is correct
3 Correct 242 ms 18552 KB Output is correct
4 Correct 1811 ms 55532 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 34192 KB Output is correct
2 Correct 720 ms 22976 KB Output is correct
3 Correct 214 ms 17656 KB Output is correct
4 Correct 2021 ms 61288 KB Output is correct