Submission #260734

#	Time	Username	Problem	Language	Result	Execution time	Memory
260734		bigg	Lottery (CEOI18_lot)	C++14	100 / 100	576 ms	8444 KiB

lot

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
#define mk(x, y) make_pair(x, y)
int v[MAXN], revid[MAXN], revk[MAXN];
std::vector<pair<int, int > > queries;
int marc[110][MAXN];
int n, l, q;
int main(){
	scanf("%d %d", &n, &l);
	for(int i = 1; i <= n; i++){
		scanf("%d",&v[i]);
	}
	

	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		int k;
		scanf("%d", &k);
		queries.push_back(mk(k, i-1));
	}
	sort(queries.begin(), queries.end());
	for(int i = 0; i < q; i++) revid[queries[i].second] = i;
	//int it1 = 0;
	for(int it2 = 0, it1 = 0; it2 <= l; it2 ++){
		while(it2 > queries[it1].first && it1 < queries.size()) it1++;
		revk[it2] = it1;
	}
	for(int it2 = 1; it2 <= n - l; it2++){
		int dif = 0;
		for(int it1 = 1; it1 <= l; it1++) dif += (v[it1] != v[it2 + it1]);
		marc[revk[dif]][1]++;
		marc[revk[dif]][1+ it2]++;
		for(int it1 = 2; it1 <= n-it2 - l + 1; it1++ ){
			dif -= (v[it1 -1] != v[it2 + it1 -1]);
			dif += (v[it1 -1 + l] != v[it2 + it1 -1 + l]);
			marc[revk[dif]][it1]++;
			marc[revk[dif]][it1 + it2]++;
		}
	}
	for(int i = 1; i < q; i++)
		for(int j = 1; j <= n; j++)
			marc[i][j] += marc[i-1][j];
	for(int i = 0; i < q; i++){
		for(int j = 1; j  <= n - l + 1; j++) printf("%d ",marc[revid[i]][j] );
		printf("\n");
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:26:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(it2 > queries[it1].first && it1 < queries.size()) it1++;
                                     ~~~~^~~~~~~~~~~~~~~~
lot.cpp:10: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:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
lot.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
lot.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20