Submission #848807

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	int n;
	int q;
	cin >> n >> q;
	vector<LL > c;
	for(int i = 0; i < q; i++){
		LL a;
		cin >> a;
		c.push_back(a);
	}
	LL m = 2e18;
	vector<LL> b;
	for(int i = q-1; i >= 0; i--){
		if(c[i] < m){
			b.push_back(c[i]);
			m = c[i];
		}
	}
	if(n < m){
		b.push_back(n);
		m = n;
	}
	map<LL,LL> freq;
	freq[b[0]] = 1;
	//cout << b[0] << endl;
	for(int i = 1; i < b.size(); i++){
		/*for(map<LL,LL>::iterator it = freq.begin(); it != freq.end(); it++){
			cout << it->first << " " << it->second << endl;
		}*/
		while(freq.rbegin()->first > b[i]){
			LL d = freq.rbegin()->first;
			//cout << b[i] << " " << d << endl;
			LL a = freq.rbegin()->second;
			//cout << d << " " << a << " " << endl;
			freq[b[i]] += (d/b[i])*a;
			freq[d%b[i]] += a;
			freq[d] = 0;
			freq.erase(d);
		}
	}
	LL diff[n+5];
	for(int i = 0; i <= n+3; i++){
		diff[i] = 0;
	}
	/*for(map<LL,LL>::iterator it = freq.begin(); it != freq.end(); it++){
		cout << it->first << " " << it->second << endl;
	}*/
	while(!freq.empty() && freq.rbegin()->first > 0){
		LL d = freq.rbegin()->first;
		LL a = freq.rbegin()->second;
		diff[d] += a;
		freq[d] = 0;
		freq.erase(d);
	}
	for(int i = m; i >= 1; i--){
		diff[i] = diff[i] + diff[i+1];
	}
	for(int i = 1; i <= n; i++){
		cout << diff[i] << endl;
	}
}

Submission Info

Judge Result