Submission #1288993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288993		semad3130	Meteors (POI11_met)	C++20	0 / 100	1161 ms	10568 KiB

met

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

using namespace std;

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;int a[m+1]={};vector<int> in[n+1];int lo=0;while((1<<lo)<m)lo++;
	for(int i = 1; i <= m; i++)cin >> a[i] , in[a[i]].push_back(i);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, ps[m+1]={};cin >> d;
	for(int da = 1; da <= d; da++){
		if(da >= cnt * k){
			cnt++;
			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 < 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 < s.size(); i1++){
				int p = s[i1];
				for(int i = 0; i < 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 = qr[i].first * (in2 - in1 + 1);
					mo[p] -= in2;
					if(mo[p] <= 0){ans[p] = qr[i].second.second;break;}
				}
			}
			qr.clear();memset(ps,0,m+1);
		}
		cin >> l >> r >> c;
		if(l < r){
			ps[l] += c;if(r != 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,{{1,r},da}});qr.push_back({c,{{l,m},da}});
		}
	}
	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 < 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 < s.size(); i1++){
			int p = s[i1];
			for(int i = 0; i < 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--;
				in2 = qr[i].first * (in2 - in1 + 1);
				mo[p] -= in2;
				if(mo[p] <= 0){ans[p] = qr[i].second.second;break;}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(ans[i] == 0)cout << "NIE\n";
		else cout << ans[i] << '\n';
	}
	return;
}

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 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