oj.uz

Submission #752190

# Submission time Handle Problem Language Result Execution time Memory
752190 2023-06-02T12:57:38 Z siewjh Meteors (POI11_met) C++17
74 / 100
 1016 ms 27344 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005;
const ll inf = 1e9 + 7;
int states, nums;
ll fw[MAXN];
void update(int x, ll v){
	while (x <= nums){
		fw[x] += v;
		x += (x & (-x));
	}
}
void rupdate(int l, int r, ll v){
	update(l, v); update(r + 1, -v);
}
ll query(int x){
	ll ans = 0;
	while (x){
		ans += fw[x];
		x -= (x & (-x));
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> states >> nums;
	vector<vector<int>> stations(states + 1);
	for (int i = 1; i <= nums; i++){
		int x; cin >> x;
		stations[x].push_back(i);
	}
	vector<ll> target(states + 1);
	for (int i = 1; i <= states; i++) cin >> target[i];
	int updates; cin >> updates;
	vector<tuple<int, int, ll>> vup(updates + 2);
	for (int i = 1; i <= updates; i++){
		int l, r; ll v; cin >> l >> r >> v;
		vup[i] = {l, r, v};
	}
	vup[updates + 1] = {1, nums, inf};
	vector<tuple<int, int, int>> vq;
	for (int i = 1; i <= states; i++) vq.push_back({1, updates + 1, i});
	vector<int> ans(states + 1, updates + 1);
	while (true){
		vector<tuple<int, int, int, int>> vm;
		for (auto x : vq){
			int l, r, s; tie(l, r, s) = x;
			if (l == r) ans[s] = l;
			else vm.push_back({(l + r) >> 1, l, r, s});
		}
		vq.clear();
		sort(vm.begin(), vm.end());
		if (vm.empty()) break;
		for (int i = 1; i <= nums; i++) fw[i] = 0;
		int ind = 0;
		for (auto x : vm){
			int l, r, m, s; tie(m, l, r, s) = x;
			for (int i = ind + 1; i <= m; i++){
				int ql, qr; ll qv; tie(ql, qr, qv) = vup[i];
				if (ql <= qr) rupdate(ql, qr, qv);
				else {
					rupdate(ql, nums, qv); rupdate(1, qr, qv);
				}
			}
			ind = m;
			ll sum = 0;
			for (int st : stations[s]) sum += query(st);
			if (sum < target[s]) vq.push_back({m + 1, r, s});
			else vq.push_back({l, m, s});
		}
	}
	for (int i = 1; i <= states; i++) {
		if (ans[i] == updates + 1) cout << "NIE\n";
		else cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3140 KB Output is correct
2 Correct 124 ms 5432 KB Output is correct
3 Correct 81 ms 4172 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3840 KB Output is correct
2 Correct 84 ms 3884 KB Output is correct
3 Correct 111 ms 5548 KB Output is correct
4 Correct 32 ms 3008 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3120 KB Output is correct
2 Correct 103 ms 5616 KB Output is correct
3 Correct 20 ms 1752 KB Output is correct
4 Correct 94 ms 4804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2828 KB Output is correct
2 Correct 83 ms 3980 KB Output is correct
3 Correct 55 ms 3024 KB Output is correct
4 Correct 106 ms 5752 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 27344 KB Output is correct
2 Incorrect 598 ms 16480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 26128 KB Output is correct
2 Incorrect 524 ms 15008 KB Output isn't correct
3 Halted 0 ms 0 KB -