Submission #752205

#	Time	Username	Problem	Language	Result	Execution time	Memory
752205		siewjh	새로운 문제 (POI11_met)	C++17	100 / 100	2154 ms	41616 KiB

met

#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 / 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