oj.uz

Submission #752205

# Submission time Handle Problem Language Result Execution time Memory
752205 2023-06-02T13:30:50 Z siewjh Meteors (POI11_met) C++17
100 / 100
 2154 ms 41616 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;
			__int128 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 1 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 1 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3024 KB Output is correct
2 Correct 117 ms 4980 KB Output is correct
3 Correct 88 ms 3864 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3516 KB Output is correct
2 Correct 85 ms 3548 KB Output is correct
3 Correct 110 ms 5196 KB Output is correct
4 Correct 33 ms 3016 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3108 KB Output is correct
2 Correct 99 ms 5276 KB Output is correct
3 Correct 20 ms 1648 KB Output is correct
4 Correct 85 ms 4440 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2600 KB Output is correct
2 Correct 84 ms 3580 KB Output is correct
3 Correct 54 ms 2752 KB Output is correct
4 Correct 108 ms 5268 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1012 ms 20184 KB Output is correct
2 Correct 185 ms 9304 KB Output is correct
3 Correct 114 ms 6732 KB Output is correct
4 Correct 1740 ms 38444 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 19012 KB Output is correct
2 Correct 558 ms 9440 KB Output is correct
3 Correct 57 ms 6860 KB Output is correct
4 Correct 2154 ms 41616 KB Output is correct