제출 #1124577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124577		inksamurai	새로운 문제 (POI11_met)	C++20	24 / 100	6094 ms	30648 KiB

met

#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);

	int n, m;
	cin >> n >> m;
	
	vector<int> a(m);
	for(int i = 0; i < m; i++){
		cin >> a[i];
		a[i] -= 1;
	}
	
	vector <vector<int>> points(n);
	for(int i = 0; i < m; i++){
		points[a[i]].push_back(i);
	}
	
	vector<int> need(n);
	for(int i = 0; i < n; i++){
		cin >> need[i];
	}
	
	int k;
	cin >> k;
	vector<pii> events(k);
	vector<int> weight(k);
	for(int i = 0; i < k; i++){
		cin >> events[i].first >> events[i].second;
		events[i].first -= 1;
		events[i].second -= 1;
		cin >> weight[i];
	}
	
	vector<int> pns(n, k);
	vector<int> ql(n, 0), qr(n, k - 1);
	for(int iter = 0; iter < 30; iter++){
		vector <vector<int>> adqry(k);
		for(int i = 0; i < n; i++){
			if(ql[i] <= qr[i]){
				int md = (ql[i] + qr[i]) / 2;
//				if(i==0) cout<<md<<"\n";
				adqry[md].push_back(i);
			}
		}
		
//		cout << ql[2] << " " <<  qr[2] << "\n";
		
		vector<int> meteors(m);
		for(int i = 0; i < k; i++){
			int l = events[i].first;
			int r = events[i].second;
			while(l != r){
				meteors[l] += weight[i];
				l += 1;
				l %= m;
			}
			meteors[r] += weight[i];
			
			for(auto id : adqry[i]){
				int now = 0;
				for(auto x : points[id]){
//					if(id == 2) cout << x << "\n";
					now += meteors[x];
				}
//				if(id == 2) cout << now << " " << i << "\n";
				if(now >= need[id]){
					pns[id] = i;
					qr[id] = i - 1;
				} else {
					ql[id] = i + 1;
				}
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		if(pns[i] == k) cout << "NIE\n";
		else cout << pns[i] + 1 << "\n";
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13