Submission #823360

#	Time	Username	Problem	Language	Result	Execution time	Memory
823360		MohamedAhmed04	Lottery (CEOI18_lot)	C++14	100 / 100	1055 ms	8692 KiB

lot

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e4 + 10 ;

int arr[MAX] , ans[MAX][110] , Cnt[MAX] , pref[MAX] ;
int Q[MAX] , Q2[MAX] ;
int n , l , q ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>l ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	cin>>q ;
	for(int i = 0 ; i < q ; ++i)
	{
		cin>>Q[i] ;
		Q2[i] = Q[i] ;
	}
	sort(Q , Q + q) ;
	for(int j = 1 ; j < n ; ++j) // distance
	{
		pref[0] = 0 ;
		for(int i = 0 ; i+j < n ; ++i)
		{
			if(i)
				pref[i] = pref[i-1] ;
			if(arr[i] != arr[i+j])
				pref[i]++ ;
		}
		for(int i = 0 ; i+j+l-1 < n ; ++i)
		{
			int x = pref[i+l-1] ;
			if(i)
				x -= pref[i-1] ;
			int idx = lower_bound(Q , Q + q , x) - Q ;
			ans[i][idx]++ ;
			ans[i+j][idx]++ ;
		}
	}
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = 1 ; j < q ; ++j)
			ans[i][j] += ans[i][j-1] ;
	}
	for(int i = 0 ; i < q ; ++i)
	{
		for(int j = 0 ; j <= n-l ; ++j)
		{
			int idx = lower_bound(Q , Q + q , Q2[i]) - Q ;
			cout<<ans[j][idx]<<" " ;
		}
		cout<<"\n" ;
	}
	return 0 ;
}		

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