답안 #71020 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71020	2018-08-24T02:33:47 Z	Diuven	Lottery (CEOI18_lot)	C++14	100 / 100	1735 ms	9132 KB

#include <bits/stdc++.h>
using namespace std;

int n, l, q, m, A[10010], cnt[101][10010], lim, now[10010], K[101], sum[10010], tmp[20010];
vector<int> X, P[10010];
vector<pair<int, int>> Q;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>l; m=n-l+1;
	for(int i=1; i<=n; i++) cin>>A[i], X.push_back(A[i]);
	cin>>q; for(int i=1; i<=q; i++) cin>>K[i], Q.push_back({K[i], i});

	sort(Q.begin(), Q.end());

	sort(X.begin(), X.end());
	lim=unique(X.begin(), X.end())-X.begin();
	X.resize(lim);

	for(int i=1; i<=n; i++) A[i]=lower_bound(X.begin(), X.end(), A[i])-X.begin();
	for(int i=1; i<=n; i++) P[A[i]].push_back(i);

	for(int i=1, lft=1, rig=0; i<=m; i++){
		while(rig+1<i+l){
			rig++;
//			cout<<"IN: "<<rig<<'\n';
			for(int j=1; j<=n; j++)
				if(A[j]==A[rig])
					tmp[j-rig+10000]++;
		}
		if(lft<i){
//			cout<<"OUT: "<<lft<<'\n';
			for(int j=1; j<=n; j++)
				if(A[j]==A[lft]) tmp[j-lft+10000]--;
			lft++;
		}

		for(int j=1; j<=n; j++) now[j]=l;

		for(int j=0; j<=20000; j++){
			int pos=i+j-10000;
			if(1<=pos && pos<=m) now[pos]-=tmp[j];
		}
/*
		for(int j=0; j<lim; j++){
			vector<int> Q;
			for(int p:P[j]) if(i<=p && p<i+l) Q.push_back(p-i);
			if(Q.empty()) continue;

			for(int p:P[j]) for(int q:Q) if(1<=p-q && p-q<=m) now[p-q]--;
		}
*/
/*
		cout<<"SOLVING: "<<i<<": \n";
		for(int s=1; s<=m; s++) cout<<now[s]<<' ';
		cout<<'\n';
		*/

		for(int j=0; j<=l; j++) sum[j]=0;
		for(int j=1; j<=m; j++) if(j!=i) sum[now[j]]++;

		for(int j=1; j<=l; j++) sum[j]+=sum[j-1];

		for(int j=0, s=0; j<(int)Q.size(); j++){
			int val, idx; tie(val,idx)=Q[j];
			while(s<val) s++;
			cnt[idx][i]=sum[s];
		}
	}
	for(int i=1; i<=q; i++, cout<<'\n') for(int j=1; j<=m; j++) cout<<cnt[i][j]<<' ';
	return 0;
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	5 ms	868 KB	Output is correct
3	Correct	6 ms	868 KB	Output is correct
4	Correct	5 ms	868 KB	Output is correct
5	Correct	4 ms	868 KB	Output is correct
6	Correct	4 ms	868 KB	Output is correct
7	Correct	5 ms	932 KB	Output is correct
8	Correct	7 ms	936 KB	Output is correct
9	Correct	6 ms	952 KB	Output is correct
10	Correct	10 ms	1012 KB	Output is correct
11	Correct	10 ms	1012 KB	Output is correct
12	Correct	8 ms	1012 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	5 ms	868 KB	Output is correct
3	Correct	6 ms	868 KB	Output is correct
4	Correct	5 ms	868 KB	Output is correct
5	Correct	4 ms	868 KB	Output is correct
6	Correct	4 ms	868 KB	Output is correct
7	Correct	5 ms	932 KB	Output is correct
8	Correct	7 ms	936 KB	Output is correct
9	Correct	6 ms	952 KB	Output is correct
10	Correct	10 ms	1012 KB	Output is correct
11	Correct	10 ms	1012 KB	Output is correct
12	Correct	8 ms	1012 KB	Output is correct
13	Correct	69 ms	1012 KB	Output is correct
14	Correct	59 ms	1144 KB	Output is correct
15	Correct	46 ms	1144 KB	Output is correct
16	Correct	66 ms	1292 KB	Output is correct
17	Correct	71 ms	1292 KB	Output is correct
18	Correct	61 ms	1292 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1687 ms	1452 KB	Output is correct
2	Correct	1637 ms	1580 KB	Output is correct
3	Correct	939 ms	1580 KB	Output is correct
4	Correct	763 ms	1580 KB	Output is correct
5	Correct	398 ms	1580 KB	Output is correct
6	Correct	702 ms	1580 KB	Output is correct
7	Correct	496 ms	1580 KB	Output is correct
8	Correct	615 ms	1580 KB	Output is correct
9	Correct	830 ms	1580 KB	Output is correct
10	Correct	800 ms	1580 KB	Output is correct
11	Correct	89 ms	1580 KB	Output is correct
12	Correct	520 ms	1616 KB	Output is correct
13	Correct	494 ms	1616 KB	Output is correct
14	Correct	515 ms	1616 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1687 ms	1452 KB	Output is correct
2	Correct	1637 ms	1580 KB	Output is correct
3	Correct	939 ms	1580 KB	Output is correct
4	Correct	763 ms	1580 KB	Output is correct
5	Correct	398 ms	1580 KB	Output is correct
6	Correct	702 ms	1580 KB	Output is correct
7	Correct	496 ms	1580 KB	Output is correct
8	Correct	615 ms	1580 KB	Output is correct
9	Correct	830 ms	1580 KB	Output is correct
10	Correct	800 ms	1580 KB	Output is correct
11	Correct	89 ms	1580 KB	Output is correct
12	Correct	520 ms	1616 KB	Output is correct
13	Correct	494 ms	1616 KB	Output is correct
14	Correct	515 ms	1616 KB	Output is correct
15	Correct	864 ms	1616 KB	Output is correct
16	Correct	708 ms	1616 KB	Output is correct
17	Correct	755 ms	1616 KB	Output is correct
18	Correct	754 ms	1616 KB	Output is correct
19	Correct	817 ms	1616 KB	Output is correct
20	Correct	749 ms	1616 KB	Output is correct
21	Correct	792 ms	1616 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	5 ms	868 KB	Output is correct
3	Correct	6 ms	868 KB	Output is correct
4	Correct	5 ms	868 KB	Output is correct
5	Correct	4 ms	868 KB	Output is correct
6	Correct	4 ms	868 KB	Output is correct
7	Correct	5 ms	932 KB	Output is correct
8	Correct	7 ms	936 KB	Output is correct
9	Correct	6 ms	952 KB	Output is correct
10	Correct	10 ms	1012 KB	Output is correct
11	Correct	10 ms	1012 KB	Output is correct
12	Correct	8 ms	1012 KB	Output is correct
13	Correct	69 ms	1012 KB	Output is correct
14	Correct	59 ms	1144 KB	Output is correct
15	Correct	46 ms	1144 KB	Output is correct
16	Correct	66 ms	1292 KB	Output is correct
17	Correct	71 ms	1292 KB	Output is correct
18	Correct	61 ms	1292 KB	Output is correct
19	Correct	1687 ms	1452 KB	Output is correct
20	Correct	1637 ms	1580 KB	Output is correct
21	Correct	939 ms	1580 KB	Output is correct
22	Correct	763 ms	1580 KB	Output is correct
23	Correct	398 ms	1580 KB	Output is correct
24	Correct	702 ms	1580 KB	Output is correct
25	Correct	496 ms	1580 KB	Output is correct
26	Correct	615 ms	1580 KB	Output is correct
27	Correct	830 ms	1580 KB	Output is correct
28	Correct	800 ms	1580 KB	Output is correct
29	Correct	89 ms	1580 KB	Output is correct
30	Correct	520 ms	1616 KB	Output is correct
31	Correct	494 ms	1616 KB	Output is correct
32	Correct	515 ms	1616 KB	Output is correct
33	Correct	864 ms	1616 KB	Output is correct
34	Correct	708 ms	1616 KB	Output is correct
35	Correct	755 ms	1616 KB	Output is correct
36	Correct	754 ms	1616 KB	Output is correct
37	Correct	817 ms	1616 KB	Output is correct
38	Correct	749 ms	1616 KB	Output is correct
39	Correct	792 ms	1616 KB	Output is correct
40	Correct	1678 ms	2908 KB	Output is correct
41	Correct	245 ms	2908 KB	Output is correct
42	Correct	687 ms	2908 KB	Output is correct
43	Correct	789 ms	2908 KB	Output is correct
44	Correct	829 ms	2908 KB	Output is correct
45	Correct	1735 ms	8868 KB	Output is correct
46	Correct	257 ms	8868 KB	Output is correct
47	Correct	892 ms	9132 KB	Output is correct
48	Correct	822 ms	9132 KB	Output is correct
49	Correct	921 ms	9132 KB	Output is correct

답안 #71020

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0