Submission #383204

#	Time	Username	Problem	Language	Result	Execution time	Memory
383204		maximath_1	Lottery (CEOI18_lot)	C++11	100 / 100	1362 ms	8496 KiB

lot

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 10005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int n, l, v[MX], q, que[BLOCK];
int sorted_que[BLOCK], ans[MX][BLOCK], pref[MX];

int main(){
	cin(n); cin(l);
	for(int i = 0; i < n; i ++)
		cin(v[i]);
	cin(q);
	for(int i = 0; i < q; i ++)
		cin(que[i]);

	for(int i = 0; i < q; i ++)
		sorted_que[i] = que[i];
	sort(sorted_que,  sorted_que + q);
	sorted_que[q] = l;

	for(int offset = 1; offset < n - l + 1; offset ++){
		for(int j = 0; j + offset < n; j ++)
			if(v[j] != v[j + offset]) pref[j] = 1;
			else pref[j] = 0;

		for(int j = 0; j + offset < n; j ++)
			pref[j] += (j ? pref[j - 1] : 0);

		for(int i = 0; i + offset < n - l + 1; i ++){
			int j = i + offset;
			int diff = pref[i + l - 1] - (i ? pref[i - 1] : 0);
			int corres = lower_bound(sorted_que, sorted_que + q + 1, diff) - sorted_que;
			ans[i][corres] ++; ans[j][corres] ++;
		}
	}

	for(int i = 0; i < n; i ++)
		for(int j = 1; j < BLOCK; j ++)
			ans[i][j] += ans[i][j - 1];

	for(int i = 0; i < q; i ++){
		int corres = lower_bound(sorted_que, sorted_que + q + 1, que[i]) - sorted_que;
		for(int j = 0; j < n - l + 1; j ++)
			printf("%d ", ans[j][corres]);
		printf("\n");
	}

	return 0;
}

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