답안 #367922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367922	2021-02-18T20:52:45 Z	ogibogi2004	Lottery (CEOI18_lot)	C++14	100 / 100	880 ms	12396 KB

lot

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10002;
int n,l,q;
int a[MAXN];
int gg[MAXN];
int p[MAXN][102];
int ans[MAXN][102];
struct query
{
	int k,pos;
	bool operator<(query const& other)const
	{
		return k<other.k;
	}
};
bool cmp(query q1,query q2)
{
	return q1.pos<q2.pos;
}
vector<query>v;
int main()
{
	cin>>n>>l;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>q;
	for(int i=0;i<q;i++)
	{
		int k;
		cin>>k;
		v.push_back({k,i});
	}
	sort(v.begin(),v.end());
	memset(gg,-1,sizeof(gg));
	for(int i=0;i<=v[0].k;i++)
	{
		gg[i]=0;
	}
	for(int i=1;i<v.size();i++)
	{
		for(int j=v[i-1].k+1;j<=v[i].k;j++)
		{
			gg[j]=i;
		}
	}
	for(int d=1;d+l<=n;d++)
	{
		int l1=1,r1=l;
		int l2=1+d,r2=l+d;
		int cnt=0;
		for(int j=1;j<=l;j++)
		{
			if(a[j]!=a[j+d])cnt++;
		}
		p[l1][gg[cnt]]++;
		p[l2][gg[cnt]]++;
		for(;;)
		{
			l1++;
			r1++;
			l2++;
			r2++;
			if(r2>n)break;
			if(a[l1-1]!=a[l2-1])cnt--;
			if(a[r1]!=a[r2])cnt++;
			p[l1][gg[cnt]]++;
			p[l2][gg[cnt]]++;
		}
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=1;i<=n;i++)
	{
		ans[i][0]=p[i][0];
	}
	for(int j=1;j<102;j++)
	{
		for(int i=1;i<=n;i++)
		{
			ans[i][j]=p[i][j]+ans[i][j-1];
		}
	}
	for(auto xd:v)
	{
		for(int i=1;i<=n-l+1;i++)
		{
			cout<<ans[i][gg[xd.k]]<<" ";
		}
		cout<<endl;
	}
return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1;i<v.size();i++)
      |              ~^~~~~~~~~

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	620 KB	Output is correct
9	Correct	1 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	620 KB	Output is correct
9	Correct	1 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	15 ms	2048 KB	Output is correct
14	Correct	9 ms	1772 KB	Output is correct
15	Correct	9 ms	1720 KB	Output is correct
16	Correct	14 ms	2028 KB	Output is correct
17	Correct	16 ms	1900 KB	Output is correct
18	Correct	14 ms	1972 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	503 ms	8556 KB	Output is correct
2	Correct	597 ms	8436 KB	Output is correct
3	Correct	311 ms	8440 KB	Output is correct
4	Correct	264 ms	8428 KB	Output is correct
5	Correct	93 ms	6508 KB	Output is correct
6	Correct	240 ms	8172 KB	Output is correct
7	Correct	120 ms	6508 KB	Output is correct
8	Correct	168 ms	7532 KB	Output is correct
9	Correct	255 ms	8428 KB	Output is correct
10	Correct	264 ms	8428 KB	Output is correct
11	Correct	19 ms	2412 KB	Output is correct
12	Correct	150 ms	6892 KB	Output is correct
13	Correct	119 ms	7020 KB	Output is correct
14	Correct	131 ms	6892 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	503 ms	8556 KB	Output is correct
2	Correct	597 ms	8436 KB	Output is correct
3	Correct	311 ms	8440 KB	Output is correct
4	Correct	264 ms	8428 KB	Output is correct
5	Correct	93 ms	6508 KB	Output is correct
6	Correct	240 ms	8172 KB	Output is correct
7	Correct	120 ms	6508 KB	Output is correct
8	Correct	168 ms	7532 KB	Output is correct
9	Correct	255 ms	8428 KB	Output is correct
10	Correct	264 ms	8428 KB	Output is correct
11	Correct	19 ms	2412 KB	Output is correct
12	Correct	150 ms	6892 KB	Output is correct
13	Correct	119 ms	7020 KB	Output is correct
14	Correct	131 ms	6892 KB	Output is correct
15	Correct	338 ms	8428 KB	Output is correct
16	Correct	228 ms	8172 KB	Output is correct
17	Correct	289 ms	8556 KB	Output is correct
18	Correct	265 ms	8556 KB	Output is correct
19	Correct	267 ms	8428 KB	Output is correct
20	Correct	281 ms	8428 KB	Output is correct
21	Correct	274 ms	8428 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	620 KB	Output is correct
9	Correct	1 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	15 ms	2048 KB	Output is correct
14	Correct	9 ms	1772 KB	Output is correct
15	Correct	9 ms	1720 KB	Output is correct
16	Correct	14 ms	2028 KB	Output is correct
17	Correct	16 ms	1900 KB	Output is correct
18	Correct	14 ms	1972 KB	Output is correct
19	Correct	503 ms	8556 KB	Output is correct
20	Correct	597 ms	8436 KB	Output is correct
21	Correct	311 ms	8440 KB	Output is correct
22	Correct	264 ms	8428 KB	Output is correct
23	Correct	93 ms	6508 KB	Output is correct
24	Correct	240 ms	8172 KB	Output is correct
25	Correct	120 ms	6508 KB	Output is correct
26	Correct	168 ms	7532 KB	Output is correct
27	Correct	255 ms	8428 KB	Output is correct
28	Correct	264 ms	8428 KB	Output is correct
29	Correct	19 ms	2412 KB	Output is correct
30	Correct	150 ms	6892 KB	Output is correct
31	Correct	119 ms	7020 KB	Output is correct
32	Correct	131 ms	6892 KB	Output is correct
33	Correct	338 ms	8428 KB	Output is correct
34	Correct	228 ms	8172 KB	Output is correct
35	Correct	289 ms	8556 KB	Output is correct
36	Correct	265 ms	8556 KB	Output is correct
37	Correct	267 ms	8428 KB	Output is correct
38	Correct	281 ms	8428 KB	Output is correct
39	Correct	274 ms	8428 KB	Output is correct
40	Correct	761 ms	9164 KB	Output is correct
41	Correct	20 ms	4972 KB	Output is correct
42	Correct	292 ms	9196 KB	Output is correct
43	Correct	271 ms	8812 KB	Output is correct
44	Correct	302 ms	8940 KB	Output is correct
45	Correct	880 ms	12268 KB	Output is correct
46	Correct	31 ms	5228 KB	Output is correct
47	Correct	388 ms	12396 KB	Output is correct
48	Correct	351 ms	10476 KB	Output is correct
49	Correct	364 ms	11116 KB	Output is correct