Submission #848095


Source Code Expand

Copy
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;


int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,q;
  cin>>n>>q;
  vector<ll> qs={n};
  rep(i,q){
    ll x;
    cin>>x;
    while(qs.size() && qs.back()>=x) qs.pop_back();
    qs.pb(x);
  }
  //cout<<qs;
  map<ll,ll> cnt;
  ll sum=qs.back();
  cnt[qs.back()]=1;
  rrep(i,qs.size()-1){
    map<ll,ll> tmp;
    for(auto it=cnt.lower_bound(qs[i]);it!=cnt.end();++it){
      tmp[it->X%qs[i]]+=it->Y;
      //cout<<*it<<"->"<<it->X%qs[i]<<endl;
      //cout<<sum<<"=>";
      sum-=it->X*it->Y;
      sum+=(it->X%qs[i])*it->Y;
      //cout<<sum<<endl;
    }
    cnt.erase(cnt.lower_bound(qs[i]),cnt.end());
    for(auto p:tmp) cnt[p.X]+=p.Y;
    cnt[qs[i]]+=(qs.back()-sum)/qs[i];
    //cout<<qs.back()-sum<<","<<qs[i]<<","<<(qs.back()-sum)%qs[i]<<endl;
    sum=qs.back();
    //  for(auto p:cnt) cout<<p;cout<<endl;
  }
  vector<ll> re(n);
  for(auto p:cnt) re[p.X]=p.Y;
  //cout<<re;
  ll s=accumulate(all(re),0ll);
  rep(i,n){
    s-=re[i];
    cout<<s<<endl;
  }
  return 0;
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User nuip
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2525 Byte
Status WA
Exec Time 1407 ms
Memory 11252 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 7
WA × 25
RE × 6
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt WA 603 ms 1536 KB
02.txt WA 609 ms 1536 KB
03.txt WA 610 ms 1664 KB
04.txt WA 614 ms 1536 KB
05.txt WA 611 ms 1536 KB
06.txt WA 796 ms 9844 KB
07.txt RE 1407 ms 10868 KB
08.txt WA 814 ms 10356 KB
09.txt WA 832 ms 8436 KB
10.txt RE 975 ms 9076 KB
11.txt WA 777 ms 9972 KB
12.txt WA 838 ms 9588 KB
13.txt RE 1012 ms 8820 KB
14.txt WA 787 ms 9844 KB
15.txt WA 793 ms 9716 KB
16.txt RE 989 ms 9204 KB
17.txt WA 815 ms 9588 KB
18.txt WA 819 ms 10100 KB
19.txt RE 962 ms 9716 KB
20.txt WA 805 ms 9204 KB
21.txt AC 879 ms 7412 KB
22.txt RE 1057 ms 11252 KB
23.txt WA 763 ms 7540 KB
24.txt WA 631 ms 2932 KB
25.txt WA 636 ms 3060 KB
26.txt AC 618 ms 2164 KB
27.txt AC 579 ms 1280 KB
28.txt WA 572 ms 1280 KB
29.txt AC 581 ms 1280 KB
30.txt WA 583 ms 1280 KB
31.txt WA 4 ms 256 KB
32.txt WA 566 ms 1280 KB
33.txt AC 4 ms 256 KB
34.txt WA 574 ms 1280 KB
35.txt WA 4 ms 256 KB
36.txt WA 4 ms 256 KB
s1.txt AC 4 ms 256 KB
s2.txt AC 4 ms 256 KB