Submission #437400

#	Time	Username	Problem	Language	Result	Execution time	Memory
437400		drkarlicio2107	Lottery (CEOI18_lot)	C++14	100 / 100	884 ms	12112 KiB

lot

#include <bits/stdc++.h>
using namespace std; int ans [110][10010]; int l[10010]; vector < pair <int, int> > qr; int prvi_veci [10010]; int ans2 [110][10010];
int main(){
	int n, d; cin >> n >> d;
	for (int i=0; i<n; i++) cin >> l[i];
	int q; cin >> q;
	for (int i=0; i<q; i++){
		int k; cin >> k;
		qr.push_back (make_pair(k, i));
	}
	for (int i=0; i<n+10; i++) prvi_veci[i]=-1;
	sort (qr.begin(), qr.end()); int last=-1;
	for (int i=0; i<qr.size(); i++){
		for (int j=qr[i].first; j>last; j--) prvi_veci [j]=i;
		last=qr [i].first;
	}
	for (int i=1; i<n-d+1; i++) {
		int l1=0; int r1=d-1;
		int l2=i; int r2=i+d-1;
		int met=0;
		for (int j=0; j<d; j++) {
			if (l[l1+j]!=l[l2+j]) met++;
		}
		int pos=prvi_veci[met];
		if (pos!=-1) ans [pos][l2]+=1;
		if (pos!=-1) ans [pos][l1]+=1;
		while (r2!=n-1){
			if (l[l1]!=l[l2]) met--;
			if (l[r1+1]!=l[r2+1]) met++;
			l1++; r1++; l2++; r2++;
			int pos=prvi_veci[met];
			if (pos!=-1) ans [pos][l2]+=1;
			if (pos!=-1) ans [pos][l1]+=1;
		}
	}
	for (int j=0; j<n-d+1; j++){
		int sol=ans [0][j];
		for (int i=1; i<q; i++){
			sol+=ans [i][j];
			ans [i][j]=sol;
		}
	}
	for (int i=0; i<q; i++) {
		int x=i; int y=qr[i].second;
		for (int j=0; j<n-d+1; j++) ans2 [y][j]=ans[x][j];
	}
	for (int i=0; i<q; i++) {
		for (int j=0; j<n-d+1; j++) cout << ans2 [i][j] << " ";
		cout << endl;
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0; i<qr.size(); i++){
      |                ~^~~~~~~~~~

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