Submission #1687867
Source Code Expand
#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif
#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long LL;
typedef pair<LL, LL> pll;
template<typename T> inline bool chkmax(T &x, const T &y) {
return x < y ? x = y, 1 : 0;
}
#ifdef DEBUG
char *input_file, *output_file;
#endif
struct IO {
static const int maxn = (1 << 25) + 10;
char a[maxn], *s, b[maxn], *t;
void INPUT() {
s = a;
t = b;
#ifdef DEBUG
FILE *f = fopen(input_file, "r");
a[fread(a, 1, sizeof a, f)] = 0;
#else
a[fread(a, 1, sizeof a, stdin)] = 0;
#endif
}
void OUTPUT() {
#ifdef DEBUG
FILE *f = fopen(output_file, "w");
fwrite(b, 1, t - b, f);
#else
fwrite(b, 1, t - b, stdout);
#endif
}
operator int() {
int x = 0;
while(*s != '-' && (*s < '0' || *s > '9')) {
++s;
}
bool f = 0;
if(*s == '-') {
f = 1;
++s;
}
while(*s >= '0' && *s <= '9') {
(x *= 10) += *s - '0';
++s;
}
if(f) {
x = -x;
}
return x;
}
operator LL() {
LL x = 0;
while(*s != '-' && (*s < '0' || *s > '9')) {
++s;
}
bool f = 0;
if(*s == '-') {
f = 1;
++s;
}
while(*s >= '0' && *s <= '9') {
(x *= 10) += *s - '0';
++s;
}
if(f) {
x = -x;
}
return x;
}
operator char() {
while(*s <= 32) {
++s;
}
char ret = *s;
++s;
return ret;
}
inline void out(int x) {
if(!x) {
*t++ = '0';
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
int y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
return;
}
inline void out(int x, char C) {
if(!x) {
*t++ = '0';
*t++ = C;
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
int y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
*t++ = C;
return;
}
inline void out(LL x) {
if(!x) {
*t++ = '0';
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
LL y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
return;
}
inline void out(LL x, char C) {
if(!x) {
*t++ = '0';
*t++ = C;
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
LL y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
*t++ = C;
return;
}
inline void out(char c) {
*t++ = c;
return;
}
inline void out(char *s) {
while(*s >= ' ') {
*t++ = *s++;
}
return;
}
}io;
void Main();
int main(int argc, char *argv[]) {
#ifdef DEBUG
input_file = argv[1];
output_file = argv[2];
#endif
io.INPUT();
Main();
io.OUTPUT();
return 0;
}
//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------
const int maxn = 1e5 + 100;
int n, m, q_n;
LL q[maxn], ans[maxn];
multiset<pll> s;
void mns(LL n) {
LL sum = 0;
for(;;) {
auto it = s.end();
--it;
if(it->X <= n) {
break;
}
sum += it->Y;
s.insert(mp(it->X - n, it->Y));
s.erase(it);
}
s.insert(mp(n, sum));
return;
}
void dvd(LL n) {
LL sum = 0;
for(;;) {
auto it = s.end();
--it;
if(it->X <= n) {
break;
}
sum += it->Y * ((it->X - 1) / n);
debug("%lld %lld\n", (it->X - 1) % n + 1, it->Y);
s.insert(mp((it->X - 1) % n + 1, it->Y));
s.erase(it);
}
debug("%lld\n", sum);
s.insert(mp(n, sum));
return;
}
void Main() {
n = io;
q_n = io;
q[m++] = n;
while(q_n--) {
q[m] = io;
while(m && q[m] <= q[m - 1]) {
q[m - 1] = q[m];
--m;
}
++m;
}
s.insert(mp(0, 0));
s.insert(mp(q[m - 1], 1));
for (int i = m - 1; i; --i) {
if(q[i] / q[i - 1] == 1) {
mns(q[i - 1]);
}
else {
dvd(q[i - 1]);
}
}
for(auto x: s) {
ans[x.X] += x.Y;
}
for (int i = n - 1; i; --i) {
ans[i] += ans[i + 1];
}
forn(i, 1, n) {
io.out(ans[i], '\n');
}
return;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1400 / 1400 |
Status |
|
|
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 |
AC |
14 ms |
8960 KB |
02.txt |
AC |
14 ms |
8960 KB |
03.txt |
AC |
15 ms |
8960 KB |
04.txt |
AC |
15 ms |
8960 KB |
05.txt |
AC |
15 ms |
8960 KB |
06.txt |
AC |
142 ms |
16000 KB |
07.txt |
AC |
136 ms |
16128 KB |
08.txt |
AC |
172 ms |
16128 KB |
09.txt |
AC |
162 ms |
16128 KB |
10.txt |
AC |
148 ms |
16000 KB |
11.txt |
AC |
151 ms |
16128 KB |
12.txt |
AC |
132 ms |
16000 KB |
13.txt |
AC |
134 ms |
16128 KB |
14.txt |
AC |
116 ms |
16000 KB |
15.txt |
AC |
123 ms |
16000 KB |
16.txt |
AC |
123 ms |
16000 KB |
17.txt |
AC |
124 ms |
16128 KB |
18.txt |
AC |
120 ms |
16000 KB |
19.txt |
AC |
105 ms |
16000 KB |
20.txt |
AC |
123 ms |
16128 KB |
21.txt |
AC |
213 ms |
12800 KB |
22.txt |
AC |
156 ms |
15744 KB |
23.txt |
AC |
183 ms |
16000 KB |
24.txt |
AC |
61 ms |
16000 KB |
25.txt |
AC |
63 ms |
15872 KB |
26.txt |
AC |
51 ms |
12672 KB |
27.txt |
AC |
5 ms |
5760 KB |
28.txt |
AC |
5 ms |
5760 KB |
29.txt |
AC |
5 ms |
5760 KB |
30.txt |
AC |
6 ms |
5760 KB |
31.txt |
AC |
2 ms |
2304 KB |
32.txt |
AC |
3 ms |
3328 KB |
33.txt |
AC |
2 ms |
2304 KB |
34.txt |
AC |
10 ms |
6528 KB |
35.txt |
AC |
2 ms |
2304 KB |
36.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |