Submission #1776334

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

ll read()
{
    ll v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

const ll INF = 2e18;
const ll N = 1e5 + 10;

ll _n, n, m, a[N], b[N], ans[N];

int main()
{
    _n = a[0] = read();
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    m = -1;
    for (int i = n; i >= 0; )
    {
        int j;
        for (j = i; j >= 0; j--)
            if (a[j] < a[i]) break;
        b[++m] = a[i];
        i = j;
    }
    reverse(b, b + m + 1);
    for (int i = 0; i <= m; i++) a[i] = b[i];
    n = m;
    for (int i = 0; i <= n; i++) b[i] = 0;
    b[n] = 1;
    for (int i = n; i >= 1; i--)
        while (1)
        {
            int t = upper_bound(a, a + i, a[i]) - a - 1;
            if (t == -1)
            {
                ans[a[i]]++;
                break;
            } else
            {
                b[t] += (a[i] / a[t]) * b[i];
                a[i] %= a[t];
            }
        }
    for (int i = a[0] - 1; i >= 1; i--)
        ans[i] += ans[i + 1];
    for (int i = 1; i <= a[0]; i++)
        printf("%lld ", ans[i] + b[0]);
    for (int i = a[0] + 1; i <= _n; i++)
        printf("0 ");
    puts("");
}

Submission Info

Judge Result