提出 #848444


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 E - Sequential operations on Sequence
ユーザ Hec
言語 C++14 (GCC 5.4.1)
得点 0
コード長 1564 Byte
結果 WA
実行時間 1137 ms
メモリ 21620 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 1400
結果
AC × 2
AC × 7
WA × 30
RE × 1
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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