Submission #1385688
Source Code Expand
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 10;
int n, q;
ll a[N], z[N];
pair<ll, int> seg[4 * N];
ll ps[N], ans[N];
void upd(int id, int p, ll vl, int s = 0, int e = q + 1){
if(e - s < 2){
seg[id].F = vl;
seg[id].S = s;
return ;
}
int mid = (s + e)/2;
if(p < mid)
upd(2*id, p, vl, s, mid);
else upd(2*id + 1, p, vl, mid, e);
if(seg[2*id].F >= seg[2*id + 1].F)
seg[id] = seg[2*id];
else seg[id] = seg[2*id + 1];
return ;
}
int get(int id, int p ,int s = 0, int e = q + 1){
if(e - s < 2)
return seg[id].F;
int mid = (s + e)/2;
if(p < mid)return get(2*id, p, s, mid);
else return get(2*id + 1, p, mid, e);
}
int main(){
cin >> n >> q;
a[0] = n;
for(int i=1; i<=q; i++)
cin >> a[i];
for(int i=q; i>=0; i--){
if(i == q){
upd(1, 0, a[q]);
z[0] = 1;
continue;
}
ll nz = 0;
while(seg[1].F >= a[i]){
ll vl = seg[1].F % a[i];
nz += (seg[1].F / a[i]) * z[seg[1].S];
upd(1, seg[1].S, vl);
}
upd(1, q - i, a[i]);
z[q - i] = nz;
}
for(int i=0; i<=q; i++){
ps[get(1, i)] += z[i];
}
ll sum = 0;
for(int i=n; i>=1; i--){
sum += ps[i];
ans[i] = sum;
}
for(int i=1; i<=n; i++)
cout << ans[i] << '\n';
}
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 |
199 ms |
10880 KB |
02.txt |
AC |
196 ms |
11008 KB |
03.txt |
AC |
190 ms |
11008 KB |
04.txt |
AC |
193 ms |
11008 KB |
05.txt |
AC |
198 ms |
11008 KB |
06.txt |
AC |
142 ms |
11008 KB |
07.txt |
AC |
162 ms |
11136 KB |
08.txt |
AC |
153 ms |
11136 KB |
09.txt |
AC |
164 ms |
11008 KB |
10.txt |
AC |
144 ms |
11008 KB |
11.txt |
AC |
134 ms |
11136 KB |
12.txt |
AC |
161 ms |
11008 KB |
13.txt |
AC |
163 ms |
11136 KB |
14.txt |
AC |
139 ms |
11008 KB |
15.txt |
AC |
135 ms |
11008 KB |
16.txt |
AC |
151 ms |
11008 KB |
17.txt |
AC |
152 ms |
11136 KB |
18.txt |
AC |
143 ms |
11008 KB |
19.txt |
AC |
131 ms |
11008 KB |
20.txt |
AC |
152 ms |
11136 KB |
21.txt |
AC |
206 ms |
9088 KB |
22.txt |
AC |
123 ms |
10752 KB |
23.txt |
AC |
152 ms |
10240 KB |
24.txt |
AC |
86 ms |
10240 KB |
25.txt |
AC |
86 ms |
10112 KB |
26.txt |
AC |
77 ms |
9088 KB |
27.txt |
AC |
53 ms |
9856 KB |
28.txt |
AC |
64 ms |
9088 KB |
29.txt |
AC |
64 ms |
9088 KB |
30.txt |
AC |
67 ms |
9088 KB |
31.txt |
AC |
2 ms |
2304 KB |
32.txt |
AC |
10 ms |
3328 KB |
33.txt |
AC |
2 ms |
2304 KB |
34.txt |
AC |
13 ms |
4608 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 |