Submission #114923

#	Time	Username	Problem	Language	Result	Execution time	Memory
114923		user202729	Lottery (CEOI18_lot)	C++17	100 / 100	348 ms	8312 KiB

lot

#include<iostream>
#include<vector>
#include<algorithm>

#ifdef _GLIBCXX_DEBUG
#define cin cin_
#include<sstream>
namespace std{
	stringstream cin(R"(
	6 2
	1 2 1 3 2 1
	2
	1
	2
	)");}
#endif

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int nn,len;std::cin>>nn>>len;
	std::vector<int> a(nn);for(int& x:a)std::cin>>x;

	int nq;std::cin>>nq;
	struct Query{
		int n,ind;
		std::vector<int> an;
	};
	std::vector<Query> qrs(nq);
	for(int k=0;k<nq;++k){
		std::cin>>qrs[k].n;
		qrs[k].ind=k;
		qrs[k].an.resize(nn-len+1);
	}
	std::sort(begin(qrs),end(qrs),[](Query const& a,Query const& b){return a.n<b.n;});

	std::vector<int> lb(len+1,-1);
	// lb[d] = min k : d <= qrs[k].n
	for(int k=nq;k--;)
		lb[qrs[k].n]=k;
	for(int d=len;d--;)
		if(lb[d]<0)
			lb[d]=lb[d+1];

	for(int del=1;del<=nn-len;++del){ // difference between two segment position
		int i=0;
		int j=del;
		int d=0;for(int z=0;z<len;++z)d+=a[z]!=a[j+z];
		while(true){
			int lbd=lb[d];
			if(lbd>=0){
				++qrs[lbd].an[i];
				++qrs[lbd].an[j];
			}

			if(j+len==nn)break;
			d-=a[i]!=a[j];
			d+=a[i+len]!=a[j+len];
			++i;++j;
		}
	}

	for(int k=1;k<nq;++k)
		for(int i=0;i<=nn-len;++i)
			qrs[k].an[i]+=qrs[k-1].an[i];

	std::sort(begin(qrs),end(qrs),[](Query const& a,Query const& b){return a.ind<b.ind;}); // may be in O(n)
	for(int k=0;k<nq;++k){
		for(int x:qrs[k].an)
			std::cout<<x<<' ';
		std::cout<<'\n';
	}
}

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