제출 #161656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161656		amoo_safar	Lottery (CEOI18_lot)	C++14	100 / 100	1118 ms	12544 KiB

lot

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
using namespace std;

typedef int ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 1e4 + 10;
const ll INF = (ll) (LONG_LONG_MAX - 3ll) / 2ll;
//const ll P = 104107;

inline ll mul(ll a, ll b){
	return (a * b) % MOD;
}

inline ll pw(ll b, ll p){
	if(p == 0) return 1;
	if(p & 1) return mul(b, pw(b, p - 1));
	return pw(mul(b,b), p / 2);
}

int a[MAXN];

vector<pll> V;

int ans[MAXN][102], del[MAXN][102];
int cnt[MAXN];
int dif[MAXN], ps[MAXN];
int num[110];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, l;
	cin >> n >> l;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int Q, k;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		cin >> k;
		k = l - k;
		V.pb({k, i});
		for(int j = k; j <= l; j++) cnt[j] ++;
	}
	sort(all(V));
	for(int i = 1; i <= Q; i++){
		num[V[i - 1].S] = i;
	}
	
	int D;
	for(int len = 1; l + len <= n; len ++){
		for(int j = 1; j + len <= n; j++) dif[j] = (a[j] == a[j + len]);
		ps[0] = 0;
		for(int j = 1; j <= n; j++) ps[j] = dif[j] + ps[j - 1];
		for(int i = 1; i + l + len - 1 <= n; i++){
			D = ps[i + l - 1] - ps[i - 1];
			del[i][0] ++;
			del[i][cnt[D] + 1] --;
			del[i + len][0] ++;
			del[i + len][cnt[D] + 1] --;
		}
	}
	
	for(int i = 1; i <= n; i++){
		ans[i][0] = del[i][0];
		for(int j = 1; j <= Q; j++) ans[i][j] = del[i][j] + ans[i][j - 1];
	}
	for(int i = 1; i <= Q; i++){
		for(int j = 1; j + l - 1 <= n; j++) cout << ans[j][num[i]] << " \n"[j + l - 1== n];
	}
	
	return 0;
}

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