Submission #847949

---

Source Code Expand

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


int main() {
	LL N,Q;
	cin >> N >> Q;
	vector<LL> pos;
	pos.push_back(0);
	pos.push_back(N);
	for(int i=0; i<Q; i++) {
		LL q;
		cin >> q;
		while(q <= pos.back())
			pos.pop_back();
		pos.push_back(q);
	}
	
//	vector<LL> nums;
	priority_queue<PII> num;
	LL mult = 1;
//	num.push(ma);
	for(int i=pos.size()-2; i>=1; i--) {
		assert(pos[i+1] > pos[i]);
		num.push(PII(pos[i+1] % pos[i], mult));
		
		mult = mult * (pos[i+1] / pos[i]);
		while(true) {
			if(num.empty()) break;
			if(num.top().first < pos[i]) break;
			PII cur = num.top(); num.pop();
			mult += cur.first / pos[i];
			num.push(PII(cur.first % pos[i], cur.second));	
		}
	}
	
	vector<LL> imos(N+1, 0);
	while(!num.empty()) {
		PII cur = num.top(); num.pop();
		if(cur.first>0)
			imos[cur.first-1] += cur.second;
	}
	for(int i=N-1; i>=0; i--) {
		imos[i] += imos[i+1];
	}
	for(int i=0; i<pos[1]; i++)
		imos[i] += mult;
	for(int i=0; i<N; i++) {
		cout << imos[i] << endl;
	}
	
	
	return 0;
}

Submission Info

Judge Result