Submission #253358

#	Time	Username	Problem	Language	Result	Execution time	Memory
253358		cfalas	Lottery (CEOI18_lot)	C++14	100 / 100	947 ms	12408 KiB

lot

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID (l+r)/2
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
 
#define EPS 1e-6
 
#define T double
int main(){
    int n, l;
    cin>>n>>l;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
	//for(int i=0;i<n;i++) cout<<a[i]<<" ";
	//cout<<endl;
	//for(int i=0;i<n;i++) cout<<a[i]<<" ";
	//cout<<endl;
 
    int q;
    cin>>q;
	vii qs;
	set<int> qus;
	map<int, vector<int> > same;
	for(int i=0;i<q;i++){
        int z;
        cin>>z;
		if(qus.count(z)==0)
			qs.push_back(ii(z, i));
		else same[z].push_back(i);
		qus.insert(z);
    }
	//cout<<l<<endl;
	qs.push_back(ii(l, q));
	sort(qs.begin(), qs.end());
	int ans[q+2][n] = {};
	//for(auto v : qs) cout<<v.F<<" "<<v.S<<endl;
	//cout<<endl;

	for(int i=1;i<n-l+1;i++){
		//cout<<"off "<<i<<endl;
		//cout<<endl;
		int dist=0;
		for(int j=0;j<l;j++){
			assert(i+j<n);
			if(a[j]!=a[i+j]) dist++;
		}
		int pos=-1;
		for(unsigned j=0;j<qs.size();j++){
			//cout<<dist<<"\n";
			assert(j<qs.size());
			if(dist<=qs[j].F) { pos = j; break;}
		}
		//cout<<endl;
		//cout<<dist<<" "<<pos<<endl;
		assert(pos!=-1);
		ans[pos][0]++, ans[pos][i]++;
		//cout<<a<<" "<<ans<<endl;
		for(int j=l;j+i<n;j++){
			//cout<<endl;
			//for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
			//cout<<"current(" <<a[j-2]<<" "<<a[j-1]<<") vs ("<<a[i+j-2]<<" "<<a[i+j-1]<<")\n";
			//cout<<"dist "<<dist<<endl;
			//cout<<"remove "<<a[j-l]<<" "<<a[i+j-l]<<endl;
			//cout<<"add "<<a[j]<<" "<<a[i+j]<<endl;
			//cout<<endl;
			if(a[j-l]!=a[i+j-l]) dist--;
			if(a[j]!=a[i+j]) dist++;
			//cout<<"new dist "<<dist<<endl;
			assert(pos>=0 && pos<(int)qs.size());
			//cout<<"old pos "<<pos<<endl;
			if(dist<=qs[pos].F){
				if(pos>0 && dist<=qs[pos-1].F) pos--;
				ans[pos][j-l+1]++, ans[pos][i+j-l+1]++;
			}
			else if(pos<q && dist<=qs[pos+1].F){
				pos++;
				ans[pos][j-l+1]++, ans[pos][i+j-l+1]++;
			}
			//cout<<"new pos "<<pos<<endl;
			assert(pos>=0 && pos<(int)qs.size());
		}
		//cout<<"-----\n";
	}
	int fin[q+2][n];
	for(int i=0;i<n;i++){
		fin[qs[0].S][i] = ans[0][i];
	}
	for(int t=1;t<qs.size();t++){
		for(int i=0;i<n-l+1;i++){
			fin[qs[t].S][i] = ans[t][i] + fin[qs[t-1].S][i];
			//cout<<qs[t].F<<" "<<qs[t].S<<endl;
			assert(qs[t].S<=q+1);
			//if(qs[t].S==7) cout<<"what\n";
			//if(qs[t].F==2) cout<<ans[t][i]<<" "<<fin[qs[t-1].S][i]<<endl;
			for(auto s_ind : same[qs[t].F]){
				fin[s_ind][i] = ans[t][i] + fin[qs[t-1].S][i];
				assert(s_ind<q);
			}
		}
	}
	for(int t=0;t<q;t++){
		for(int i=0;i<n-l+1;i++) cout<<fin[t][i]<<" ";
		cout<<endl;
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t=1;t<qs.size();t++){
              ~^~~~~~~~~~

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