Submission #1289096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289096		semad3130	새로운 문제 (POI11_met)	C++20	100 / 100	4954 ms	24924 KiB

met

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef pair<int,int> pii;
const int maxn = 3e5 + 100;

typedef pair<pii,int> pi2;
typedef pair<int,pi2> pi3;
int n, m, k, d;

void seyyed(){
	cin >> n >> m;vector<int> a(m+1), in[n+1];
	for(int i = 1; i <= m; i++)cin >> a[i], in[a[i]].push_back(i);
	vector<bool> mark(n+1);vector<int> mo(n+1), mo1(n+1), ans(n+1);vector<pi3> qr;
	for(int i = 1; i <= n; i++)cin >> mo[i];
	k = 120; int cnt = 1, l, r, c; cin >> d;
	vector<long long> ps(m+2,0);
	for(int da = 1; da <= d; da++){
		cin >> l >> r >> c;
		if(l <= r){
			ps[l] += c;
			if(r + 1 <= m) ps[r+1] -= c;
			qr.push_back({c,{{l,r},da}});
		}else{
			ps[l] += c;
			ps[1] += c;
			if(r + 1 <= m) ps[r+1] -= c;
			qr.push_back({c,{{1ll,r},da}});
			qr.push_back({c,{{l,m},da}});
		}
		if(da % k == 0){
			for(int i = 1; i <= m; i++)ps[i] += ps[i-1];
			vector<int> s;
			for(int i = 1; i <= n; i++){
				if(mark[i])continue;
				for(int g = 0; g < (int)in[i].size(); g++) mo1[i] += ps[in[i][g]];
				if(mo[i] - mo1[i] > 0) mo[i] -= mo1[i], mo1[i] = 0;
				else s.push_back(i), mark[i]=1;
			}
			for(int i1 = 0; i1 < (int)s.size(); i1++){
				int p = s[i1];
				for(int i = 0; i < (int)qr.size(); i++){
					int L = qr[i].second.first.first, R = qr[i].second.first.second;
					int in1 = lower_bound(in[p].begin(), in[p].end(), L)-in[p].begin();
					int in2 = upper_bound(in[p].begin(), in[p].end(), R)-in[p].begin();in2--;
					int cnt = in2 - in1 + 1;
					if(cnt <= 0) continue;
					long long pu = 1LL * qr[i].first * cnt;
					mo[p] -= pu;
					if(mo[p] <= 0){ans[p] = qr[i].second.second;break;}
				}
			}
			qr.clear(), fill(ps.begin(), ps.end(), 0);
		}
	}
	if(qr.size()){
		for(int i = 1; i <= m; i++)ps[i] += ps[i-1];
		vector<int> s;
		for(int i = 1; i <= n; i++){
			if(mark[i])continue;
			for(int g = 0; g < (int)in[i].size(); g++)mo1[i] += ps[in[i][g]];
			if(mo[i] - mo1[i] <= 0)s.push_back(i);
		}
		for(int i1 = 0; i1 < (int)s.size(); i1++){
			int p = s[i1];
			for(int i = 0; i < (int)qr.size(); i++){
				int L = qr[i].second.first.first, R = qr[i].second.first.second;
				int in1 = lower_bound(in[p].begin(), in[p].end(), L)-in[p].begin();
				int in2 = upper_bound(in[p].begin(), in[p].end(), R)-in[p].begin();in2--;
				int cnt = in2 - in1 + 1;
				if(cnt <= 0) continue;
				long long pu = 1LL * qr[i].first * cnt;
				mo[p] -= pu;
				if(mo[p] <= 0){ans[p] = qr[i].second.second;break;}
			}
		}
	}

	for(int i = 1; i <= n; i++){
		if(ans[i] == 0) cout << "NIE";
		else cout << ans[i];
		if(i != n) cout <<'\n';
	}
	return;
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	seyyed();
}

• 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