Submission #848444


Source Code Expand

Copy
#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

ll ary[100010];
map<ll,ll> cnt;

vector<ll> order;

ll ans[100010];

int main(void){
	int n,q;
	cin >> n >> q;
	rep(i,q) cin >> ary[i];

	ll cur=1LL<<60;
	rrep(i,q){
		if(cur>ary[i]){
			order.push_back(ary[i]);
			cur=ary[i];
		}
	}

	cnt[order[0]]++;
	const int m=order.size();
	rep(i,1,m){
		ll num=cnt[order[i-1]]*(order[i-1]/order[i]);
		ll add=cnt[order[i-1]];
		cnt[order[i-1]]=0;
		cnt[order[i]]+=num;
		if(order[i-1]%order[i]!=0) cnt[order[i-1]%order[i]]+=add;
	}

	//rep(i,1,n+1) cout << cnt[i] << endl;

	rep(i,1,n+1) ans[1]+=cnt[i],ans[i+1]-=cnt[i];
	rep(i,1,n+1) ans[i]+=ans[i-1];
	rep(i,1,n+1) cout << ans[i] << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User Hec
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1564 Byte
Status WA
Exec Time 1137 ms
Memory 21620 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 7
WA × 30
RE × 1
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 WA 839 ms 8192 KB
02.txt WA 852 ms 8192 KB
03.txt WA 859 ms 8192 KB
04.txt WA 849 ms 8192 KB
05.txt WA 864 ms 8192 KB
06.txt WA 977 ms 20084 KB
07.txt WA 983 ms 20084 KB
08.txt WA 991 ms 20084 KB
09.txt WA 964 ms 20084 KB
10.txt WA 974 ms 20084 KB
11.txt WA 980 ms 20084 KB
12.txt WA 971 ms 20084 KB
13.txt WA 976 ms 20084 KB
14.txt WA 1015 ms 20212 KB
15.txt WA 982 ms 20084 KB
16.txt WA 985 ms 20084 KB
17.txt WA 981 ms 20084 KB
18.txt WA 981 ms 20084 KB
19.txt WA 993 ms 20084 KB
20.txt WA 994 ms 20084 KB
21.txt WA 1072 ms 21620 KB
22.txt WA 1064 ms 21620 KB
23.txt WA 1137 ms 21492 KB
24.txt WA 906 ms 15220 KB
25.txt WA 901 ms 15220 KB
26.txt WA 861 ms 14196 KB
27.txt AC 727 ms 8192 KB
28.txt AC 737 ms 8192 KB
29.txt AC 721 ms 8192 KB
30.txt WA 728 ms 8192 KB
31.txt AC 4 ms 256 KB
32.txt RE 189 ms 256 KB
33.txt AC 4 ms 256 KB
34.txt WA 645 ms 7424 KB
35.txt WA 4 ms 256 KB
36.txt WA 4 ms 256 KB
s1.txt AC 4 ms 256 KB
s2.txt AC 4 ms 256 KB