답안 #95184 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95184	2019-01-28T09:35:55 Z	Retro3014	Lottery (CEOI18_lot)	C++17	100 / 100	1684 ms	6776 KB

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

#define MAX_N 100000
#define MAX_Q 100

using namespace std;

int N, L, Q;
//short ans[MAX_Q+1][MAX_N+1];
short calc2[MAX_Q+1][MAX_N+1];
int v[MAX_N+1];

struct Query{
	Query (int idx, int data) : idx(idx), data(data) {}
	int idx, data;
	bool operator <(const Query &a)const{
		return data<a.data;
	}
};
vector<Query> query;
vector<int> q;

void calc(int x, int y){
	y = lower_bound(q.begin(), q.end(), y)-q.begin();
	calc2[y][x]++;
}

int main(){
	scanf("%d %d", &N, &L);
	int x;
	for(int i=0; i<N; i++){
		scanf("%d", &v[i]);
	}
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		scanf("%d", &x);	query.push_back({i, x});
		q.push_back(x);
	}
	sort(q.begin(), q.end()); sort(query.begin(), query.end());
	for(int i=1; i+L-1<N; i++){
		int s1 = 0, s2 = i, e1 = -1, e2 = i-1;
		int cnt=0;
		while(e2<N){
			if(e1-s1+1 == L){
				calc(s1, cnt); calc(s2, cnt);
				//printf("%d %d %d\n", s1, s2, cnt);
				cnt-=(v[s1]!=v[s2]); s1++; s2++;
			}else{
				e1++; e2++;
				if(e2==N)	break;
				cnt+=(v[e1]!=v[e2]);
			}
		}
	}
	for(int i=0; i<Q; i++){
		if(i==0)	continue;
		for(int j=0; j<N; j++){
			calc2[i][j] += calc2[i-1][j];
		}
	}Query tmp = query[0];
	short t;
	for(int i=0; i<Q; i++){
		for(int j=i+1; j<Q; j++){
			if(query[i].idx>query[j].idx){
				tmp = query[i]; query[i] = query[j]; query[j] = tmp;
				for(int k=0; k<N; k++){
					t = calc2[i][k]; calc2[i][k] = calc2[j][k]; calc2[j][k] = t;
				}
			}
		}
	}
	for(int i=0; i<Q; i++){
		for(int j=0; j<N-L+1; j++){
			printf("%d ", calc2[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~
lot.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
lot.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); query.push_back({i, x});
   ~~~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	38 ms	376 KB	Output is correct
14	Correct	26 ms	632 KB	Output is correct
15	Correct	21 ms	504 KB	Output is correct
16	Correct	39 ms	636 KB	Output is correct
17	Correct	34 ms	632 KB	Output is correct
18	Correct	34 ms	504 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	601 ms	464 KB	Output is correct
2	Correct	552 ms	504 KB	Output is correct
3	Correct	539 ms	504 KB	Output is correct
4	Correct	530 ms	632 KB	Output is correct
5	Correct	177 ms	632 KB	Output is correct
6	Correct	491 ms	648 KB	Output is correct
7	Correct	150 ms	504 KB	Output is correct
8	Correct	251 ms	632 KB	Output is correct
9	Correct	515 ms	632 KB	Output is correct
10	Correct	531 ms	608 KB	Output is correct
11	Correct	27 ms	376 KB	Output is correct
12	Correct	290 ms	492 KB	Output is correct
13	Correct	228 ms	632 KB	Output is correct
14	Correct	231 ms	632 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	601 ms	464 KB	Output is correct
2	Correct	552 ms	504 KB	Output is correct
3	Correct	539 ms	504 KB	Output is correct
4	Correct	530 ms	632 KB	Output is correct
5	Correct	177 ms	632 KB	Output is correct
6	Correct	491 ms	648 KB	Output is correct
7	Correct	150 ms	504 KB	Output is correct
8	Correct	251 ms	632 KB	Output is correct
9	Correct	515 ms	632 KB	Output is correct
10	Correct	531 ms	608 KB	Output is correct
11	Correct	27 ms	376 KB	Output is correct
12	Correct	290 ms	492 KB	Output is correct
13	Correct	228 ms	632 KB	Output is correct
14	Correct	231 ms	632 KB	Output is correct
15	Correct	470 ms	504 KB	Output is correct
16	Correct	463 ms	632 KB	Output is correct
17	Correct	546 ms	632 KB	Output is correct
18	Correct	539 ms	604 KB	Output is correct
19	Correct	530 ms	632 KB	Output is correct
20	Correct	532 ms	580 KB	Output is correct
21	Correct	530 ms	504 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	38 ms	376 KB	Output is correct
14	Correct	26 ms	632 KB	Output is correct
15	Correct	21 ms	504 KB	Output is correct
16	Correct	39 ms	636 KB	Output is correct
17	Correct	34 ms	632 KB	Output is correct
18	Correct	34 ms	504 KB	Output is correct
19	Correct	601 ms	464 KB	Output is correct
20	Correct	552 ms	504 KB	Output is correct
21	Correct	539 ms	504 KB	Output is correct
22	Correct	530 ms	632 KB	Output is correct
23	Correct	177 ms	632 KB	Output is correct
24	Correct	491 ms	648 KB	Output is correct
25	Correct	150 ms	504 KB	Output is correct
26	Correct	251 ms	632 KB	Output is correct
27	Correct	515 ms	632 KB	Output is correct
28	Correct	531 ms	608 KB	Output is correct
29	Correct	27 ms	376 KB	Output is correct
30	Correct	290 ms	492 KB	Output is correct
31	Correct	228 ms	632 KB	Output is correct
32	Correct	231 ms	632 KB	Output is correct
33	Correct	470 ms	504 KB	Output is correct
34	Correct	463 ms	632 KB	Output is correct
35	Correct	546 ms	632 KB	Output is correct
36	Correct	539 ms	604 KB	Output is correct
37	Correct	530 ms	632 KB	Output is correct
38	Correct	532 ms	580 KB	Output is correct
39	Correct	530 ms	504 KB	Output is correct
40	Correct	1116 ms	1656 KB	Output is correct
41	Correct	29 ms	1016 KB	Output is correct
42	Correct	1027 ms	1868 KB	Output is correct
43	Correct	977 ms	1528 KB	Output is correct
44	Correct	976 ms	1528 KB	Output is correct
45	Correct	1684 ms	6724 KB	Output is correct
46	Correct	59 ms	3192 KB	Output is correct
47	Correct	1574 ms	6776 KB	Output is correct
48	Correct	1321 ms	5112 KB	Output is correct
49	Correct	1325 ms	5752 KB	Output is correct

답안 #95184

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