Submission #827081

#	Time	Username	Problem	Language	Result	Execution time	Memory
827081		sentheta	Lottery (CEOI18_lot)	C++17	100 / 100	355 ms	12384 KiB

lot

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}










const int N = 1e4+5;
const int Q = 105;

int n, len, q;
int a[N];

// point to next possible query
int ptr[N];
int find(int x){
	if(ptr[x]==x) return x;
	return ptr[x] = find(ptr[x]);
}

int qrys[Q];
V<int> ans[N];


void solve(){
	
	cin >> n >> len;
	
	rep(i,0,n){
		cin >> a[i];
	}
	
	rep(i,0,N) ptr[i] = i+1;
	ptr[N-1] = N-1;
	
	cin >> q;
	rep(i,0,q){
		cin >> qrys[i];
		
		ptr[qrys[i]] = qrys[i];
	}
	rep(i,0,N) if(ptr[i]==i){
		ans[i] = V<int>(n-len+1);
	}
	
	
	// consider all shifts	
	for(int sh=1; sh+len-1<n; sh++){
		int i=0, j=sh;
		
		// compare first
		int diff = 0;
		rep(k,0,len){
			diff += a[i+k]!=a[j+k];
		}
		ans[find(diff)][i]++;
		ans[find(diff)][j]++;
		
		// continue comparison
		i++; j++;
		for(; j+len-1<n; i++,j++){
			diff -= a[i-1]!=a[j-1];
			diff += a[i+len-1]!=a[j+len-1];
			
			// {
			// 	int tmp=0;
			// 	rep(k,0,len){
			// 		tmp += a[i+k]!=a[j+k];
			// 	}
			// 	assert(tmp==diff);
			// }

			ans[find(diff)][i]++;
			ans[find(diff)][j]++;
		}
	}
	
	
	
	// cumulative sum
	int prv = -1;
	rep(i,0,N) if(!ans[i].empty()){
		if(prv==-1){
			prv = i; continue;
		}
		rep(j,0,n-len+1){
			ans[i][j] += ans[prv][j];
		}
		prv = i;
	}
	
	
	rep(i,0,q){
		for(int x : ans[qrys[i]]){
			cout << x << " ";
		}
		cout << nl;
	}
	
	
	
}

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