Submission #95184

#	Time	Username	Problem	Language	Result	Execution time	Memory
95184		Retro3014	Lottery (CEOI18_lot)	C++17	100 / 100	1684 ms	6776 KiB

lot

#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 (stderr)

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 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20