Submission #825987

#	Time	Username	Problem	Language	Result	Execution time	Memory
825987		Tsovak	Lottery (CEOI18_lot)	C++17	100 / 100	529 ms	6408 KiB

lot

// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;
 
// -------------------- Typedefs -------------------- //
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
 
// -------------------- Defines -------------------- //
 
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
 
#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue
 
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
 
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ft front
#define bk back
 
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
 
// -------------------- Constants -------------------- //
 
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);
 
// -------------------- Functions -------------------- //
 
void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}
 
void precision(int x)
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}
 
ll gcd(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}
 
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
 
bool is_prime(ll a)
{
	if (a == 1) {
		return false;
	}
	for (ll i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			return false;
		}
	}
	return true;
}
 
bool is_square(ll a)
{
	ll b = ll(sqrt(a));
	return (b * b == a);
}
 
bool is_cube(ll a)
{
	ll b = ll(cbrt(a));
	return (b * b * b == a);
}
 
int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}
 
ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
		}
		b >>= 1;
		a *= a;
	}
	return ans;
}
 
ll binpow_by_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
			ans %= mod;
		}
		b >>= 1;
		a *= a;
		a %= mod;
	}
	return ans;
}
 
ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) {
		ans *= ll(i);
	}
	return ans;
}
 
ll factorial_by_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) {
		ans *= ll(i);
		ans %= mod;
	}
	return ans;
}
 
// -------------------- Solution -------------------- //
 
const short N = 10005, Q = 105;
int aa[N];
short a[N];
map<int, short> mp;
bool bb[N];
short h[N];
short hh[N];
short p[N][Q];
short qw[Q];
short n, l, q;
 
void comp()
{
	int i, j;
 
	set<int> st;
 
	for (i = 1; i <= n; i++) st.insert(aa[i]);
 
	j = 0;
 
	for (auto x : st) {
		j++;
		mp[x] = j;
	}
 
	for (i = 1; i <= n; i++) {
		a[i] = mp[aa[i]];
	}
 
	return;
}
 
vector<short> v;
 
void calc()
{
	short i, j;
 
	queue<short> q1, q2;
 
	short m = n - l + 1;
	short r;
 
	short x, y;
 
	for (i = 0; i <= l; i++) {
		j = lb(all(v), i) - v.begin();
 
		hh[i] = j + 1;
	}
 
	for (i = 1; i < m; i++) {
		while (!q1.empty()) q1.pop();
		while (!q2.empty()) q2.pop();
 
		r = 0;
		for (j = 1; j <= l; j++) {
			if (a[j] != a[j + i]) r++;
			q1.push(a[j]);
			q2.push(a[j + i]);
		}
 
		p[1][hh[r]]++;
		p[i + 1][hh[r]]++;
 
		for (j = i + 2; j <= m; j++) {
			x = q1.ft(); q1.pop();
			y = q2.ft(); q2.pop();
			if (x != y) r--;
 
			x = a[j + l - 1];
			y = a[j - i + l - 1];
 
			if (x != y) r++;
			q1.push(x);
			q2.push(y);
 
			p[j - i][hh[r]]++;
			p[j][hh[r]]++;
		}
	}
 
	return;
}
 
void solve()
{
	short i, j, k;
 
	cin >> n >> l;
	for (i = 1; i <= n; i++) cin >> aa[i];
	comp();
 
	cin >> q;
	for (i = 1; i <= q; i++) {
		cin >> qw[i];
		bb[qw[i]] = true;
 
		if (l == n) cout << "0\n";
	}
 
	if (l == n) return;
 
	for (i = 0; i <= l; i++) if (bb[i]) v.pb(i);
	for (i = 0; i < sz(v); i++) h[v[i]] = i + 1;
 
	calc();
 
	//for (i = 1; i <= n - l + 1; i++) {
	//	for (j = 1; j <= sz(v); j++) cout << p[i][j] << ' ';
	//	cout << "\n";
	//}
 
	for (i = 1; i <= n - l + 1; i++) {
		p[i][0] = 0;
		for (j = 1; j <= sz(v); j++) p[i][j] += p[i][j - 1];
	}
 
	//for (i = 0; i <= l; i++) cout << hh[i] << ' ';
	//cout << ".\n";
	
 
	for (i = 1; i <= q; i++) {
		for (j = 1; j <= n - l + 1; j++) {
			cout << p[j][hh[qw[i]]] << ' ';
		}
		cout << "\n";
	}
 
	return;
}
 
void precalc()
{
	return;
}
 
int main()
{
	fastio();
 
	precalc();
 
	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}
 
	//cout << db(clock()) / CLOCKS_PER_SEC << endl;
 
	return 0;
}
 
/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Compilation message (stderr)

lot.cpp: In function 'void solve()':
lot.cpp:291:14: warning: unused variable 'k' [-Wunused-variable]
  291 |  short i, j, k;
      |              ^

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