Submission #846966

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VI mq;
map<in,in> qc;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,q;
  cin>>n>>q;
  mq.resize(q);
  forn(i,q)
    cin>>mq[i];
  reverse(all(mq));
  in rr=1;
  for(in i=1;i<q;++i){
    if(mq[i]<mq[rr-1])
      mq[rr++]=mq[i];
  }
  mq.resize(rr);
  reverse(all(mq));
  qc[-mq.back()]=1;
  map<in,in>::iterator it;
  in id;
  while(1){
    it=qc.begin();
    if(-it->first<=mq[0])
      break;
    id=lower_bound(all(mq),-it->first)-mq.begin();
    --id;
    qc[-mq[id]]+=(-it->first)/mq[id]*it->second;
    qc[-((-it->first)%mq[id])]+=it->second;
    qc.erase(it);
  }
  in tt=0;
  fors(i,qc)
    tt+=i->second;
  tt-=qc[0];
  for(in i=1;i<=n;++i){
    cout<<tt<<"\n";
    tt-=qc[-i];
  }
  return 0;
}

Submission Info

Judge Result