Submission #72891

#	Time	Username	Problem	Language	Result	Execution time	Memory
72891		zscoder	Lottery (CEOI18_lot)	C++17	100 / 100	2265 ms	13324 KiB

lot

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 10011;
int dp[N];
int a[N];

void addrange(int l, int r)
{
	l=max(l,0);
	r=min(r,N-2);
	dp[l]++; dp[r+1]--;
}

void reset()
{
	memset(dp,0,sizeof(dp));
}

void push()
{
	for(int i=1;i<N;i++)
	{
		dp[i]+=dp[i-1];
	}
}

bool valid(int x, int n)
{
	return (x>=0&&x<n);
}

vector<ii> queries;
int pref[11111];
int ans[111][11111];
int sorted[11111][111];

void solve(int n, int l, int d)
{
	reset();
	for(int i=0;i<n;i++)
	{
		if(valid(i+d,n)&&a[i]==a[i+d])
		{
			addrange(i-l+1,i);
		}
	}
	push();
	for(int i=0;i<=n-l;i++)
	{
		if(!valid(i+d,n-l+1)) continue;
		int mx = pref[dp[i]];
		mx--;
		if(mx>=0)
		{
			sorted[i][mx]++;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,l; cin>>n>>l;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int q; cin>>q;
	for(int i=0;i<q;i++)
	{
		int d; cin>>d; d = l-d;
		queries.pb(mp(d,i));
	}
	sort(queries.begin(),queries.end());
	for(int i=0;i<q;i++)
	{
		pref[queries[i].fi]++;
	}
	for(int i=1;i<=n;i++)
	{
		pref[i]+=pref[i-1];
	}
	for(int d=-n;d<=n;d++)
	{
		if(d==0) continue;
		solve(n,l,d);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=q-1;j>=0;j--)
		{
			sorted[i][j]+=sorted[i][j+1];
		}
		for(int j=0;j<q;j++)
		{
			ans[queries[j].se][i] = sorted[i][j];
		}
	}
	for(int i=0;i<q;i++)
	{
		for(int j=0;j<n-l+1;j++)
		{
			cout<<ans[i][j];
			if(j+1<n-l+1) cout<<' ';
		}
		cout<<'\n';
	}
}

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