Submission #169554

#	Time	Username	Problem	Language	Result	Execution time	Memory
169554		alishahali1382	Lottery (CEOI18_lot)	C++14	100 / 100	585 ms	8568 KiB

lot

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 10010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int A[MAXN];
int K[MAXN];
int tof[MAXN];
int ans[105][MAXN];
int query[MAXN];
vector<int> Q;

void add(int i, int j, int x){
	//cerr<<i<<' '<<j<<"  "<<x<<endl;
	int ind=tof[x];
	ans[ind][i]++;
	ans[ind][j]++;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k;
	for (int i=1; i<=n; i++) cin>>A[i];
	cin>>m;
	for (int i=1; i<=m; i++) cin>>query[i], Q.pb(query[i]);
	//Q.pb(k+1);
	sort(all(Q));
	Q.resize(unique(all(Q))-Q.begin());
	//debugv(Q)
	for (int i=0; i<=n; i++) tof[i]=lower_bound(all(Q), i)-Q.begin();
	
	for (int i=k+1; i<=n; i++){
		int val=0;
		for (int j=0; j<k; j++) val+=(A[i-j]!=A[k-j]);
		add(k, i, val);
		for (int j=1; i+j<=n; j++){
			val+=(A[j+k]!=A[i+j])-(A[j]!=A[i+j-k]);
			add(j+k, i+j, val);
		}
	}
	
	for (int i=1; i<=n; i++) for (int j=1; j<105; j++) ans[j][i]+=ans[j-1][i];
	for (int id=1; id<=m; id++){
		for (int i=k; i<=n; i++) cout<<ans[tof[query[id]]][i]<<" \n"[i==n];
	}
	
	return 0;
}

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