Submission #881359

---

Source Code Expand

/*
	Swamy Saranam

	Date	: 13/09/2016 14:57:03
	Author	: Krishna Mohan A M
	Problem	: E - Sequential operations on Sequence
	Status	:
*/
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

typedef long long ll;
typedef pair<int,int>	pii;
typedef pair<ld,ld>	pdd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef pair<ll,ll> pl;

#define FASTIO          ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define FOR(i,a,b)		for(int i=(a);i<(b);i++)
#define REP(i,n)		FOR(i,0,n)
#define SORT(v)			sort((v).begin(),(v).end())
#define UN(v)			SORT(v),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define CL(a,b)			memset(a,b,sizeof a)
#define pb				push_back
#define x               first
#define y               second
#define endl            "\n"
#define sendl           " \n"
#define all(x)          (x).begin(), (x).end()

const int mod = 1000000007;
ll a[100005];

int main()
{
    FASTIO
    int n, q;
    cin>>n>>q;
    vector<ll> stk;
    stk.pb(n);
    REP(i, q)
    {
      ll tmp;
      cin>>tmp;
      while(!stk.empty() && stk.back() > tmp)
        stk.pop_back();
      stk.pb(tmp);
    }
    int k = stk.size();
    vector<ll> t(k);
    t[k-1] = 1;
    for(int i=k-1; i>=0; i--)
    {
      if(!i){
        a[stk[i]] += t[i];
        break;
      }
      ll p = t[i];
      ll z = stk[i];
      stk[i] = 2e18; //setting it as max value
      while(z > stk[0]){
        int j = lower_bound(all(stk), z) - stk.begin()-1;
        t[j] += p*(z/stk[j]);
        z%=stk[j];
      }
      a[z] += p;
    }
    for(int i=n-1; i>=0; i--)
        a[i] += a[i+1];
    FOR(i, 1, n+1)
      cout<<a[i]<<endl;
    #ifdef LOCAL_DEFINE
      cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}

Submission Info

Judge Result