Submission #848465

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int maxlog = 70;
const int maxN = 100100, maxq = 100100;

int N, n;
LL a[maxq + 5];

struct data
{
	LL num[maxN + 5];

	data() { memset(num, 0, sizeof num); }
	
	friend data operator+(const data &x, const data &y)
	{
		data ans;
		REP(i, 0, N) ans.num[i] = x.num[i] + y.num[i];
		return ans;
	}

	data &operator+=(const data &x)
	{
		REP(i, 0, N) num[i] += x.num[i];
		return *this;
	}
	
	friend data operator*(const data &x, const LL &y)
	{
		data ans;
		REP(i, 0, N) ans.num[i] = x.num[i] * y;
		return ans;
	}

	data &operator*=(const LL &x)
	{
		REP(i, 0, N) num[i] *= x;
		return *this;
	}

	void print()
	{
		REP(i, 0, N) debug("%lld ", num[i]);
	}

};

int tot = 0;
data val[maxlog + 5];
LL len[maxlog + 5];

vector<LL> all;

inline data calc(int id)
{
	if (!id)
	{
		data ret;
		for (auto u : all) if (u > 0) ++ret.num[u - 1];
		for (int i = N - 2; i >= 0; --i) ret.num[i] += ret.num[i + 1];
		return ret;
	}
	LL cnt = 0;
	for (auto &u : all)
	{
		cnt += u / len[id - 1];
		u %= len[id - 1];
	}
	data ret = val[id - 1] * cnt;
	ret += calc(id - 1);
	return ret;
}

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int qn;
	scanf("%d%d", &N, &qn);
	LL x;
	n = 0;
	a[n++] = N;
	REP(i, 0, qn)
	{
		scanf("%" LLFORMAT "d", &x);
		while (n && a[n - 1] >= x) --n; 
		a[n++] = x;
	}
	int lst = 0;
	REP(i, 0, a[0]) val[0].num[i] = 1;
	len[0] = a[0];
	++tot;
	REP(i, 1, n)
	{
		if (!~lst || a[i] >= (a[lst] << 1) || (i == n - 1))
		{
			len[tot] = a[i];
			val[tot] = calc(tot - 1);
			val[tot] += val[tot - 1];
			val[tot] *= a[i] / a[i - 1];
			all.clear();
			all.pb(a[i] % a[i - 1]);
			val[tot] += calc(tot - 1);
			++tot;
			all.clear();
			lst = i;
		}
		else all.pb(a[i] - a[i - 1]);
	}
	REP(i, 0, N) printf("%" LLFORMAT "d\n", val[tot - 1].num[i]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:107:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &qn);
                        ^
./Main.cpp:113:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%" LLFORMAT "d", &x);
                              ^

Judge Result