제출 #147251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147251		miguel	Lottery (CEOI18_lot)	C++14	100 / 100	966 ms	13048 KiB

lot

/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define int ll
const ll mod = 998244353;
const ll nmax=1000003;
#define int ll
int n, l, a[10010], dif[10010], ans[10010][110], q;//idx, k
int up[10010];
vector<pi> v;//query, idx of query

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>l;
    for(int i=1; i<=n; i++) cin>>a[i];
	cin>>q;
	for(int i=1; i<=q; i++){
		int k;
		cin>>k;
		v.pb({k, i});
	}
	sort(v.begin(), v.end());
	int pr=-1;
	for(pi i : v){
		for(int j=pr+1; j<=i.x; j++) up[j]=i.y;
		pr=i.x;
	}
	
    for(int d=1; d<=n-l; d++){
		memset(dif, 0, sizeof dif);
		for(int i=1; i<=n-d; i++){
			if(a[i]!=a[i+d]) dif[i]++, dif[min(i+l, n+1)]--;
		}
		for(int i=1; i<=n-d; i++){
			dif[i]+=dif[i-1];
			//if(d==1) cout<<i-l+1<<" "<<dif[i]<<endl;
			if(i>=l && dif[i]<=pr) ans[i-l+1][up[dif[i]]]++, ans[i-l+1+d][up[dif[i]]]++;
		}
	}
	pr=0;
	for(int i=1; i<=n-l+1; i++){
		pr=0;
		for(pi k: v)  ans[i][k.y]+=ans[i][pr], pr=k.y;
	}
	for(int i=1; i<=q; i++){
		for(int id=1; id<=n-l+1; id++) cout<<ans[id][i]<<" "; 
		cout<<"\n";
	}
}

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