Submission #546444

#	Time	Username	Problem	Language	Result	Execution time	Memory
546444		aryan12	Lottery (CEOI18_lot)	C++17	60 / 100	837 ms	1100 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

vector<pair<int, int> > queries;


bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.second < b.second;
}

int BS(int val)
{
	int ans = -1;
	int l = 0, r = queries.size() - 1;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(queries[mid].first < val)
		{
			l = mid + 1;
			ans = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	return ans + 1;
}

void Solve() 
{
	int n, l;
	cin >> n >> l;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++)
	{
		int x;
		cin >> x;
		queries.push_back(make_pair(x, i));
	}
	queries.push_back({1e18, 1e18});
	sort(queries.begin(), queries.end());
	vector<int> next_high(l + 1);
	for(int i = 0; i <= l; i++)
	{
		int pos = BS(i);
		next_high[i] = pos;
		//cout << next_high[i] << " ";
	}
	//cout << "\n";
	map<int, int> idk;
	idk[next_high[0]] = 0;
	int cnt = 1;
	for(int i = 1; i <= l; i++)
	{
		if(next_high[i] != next_high[i - 1])
		{
			idk[next_high[i]] = cnt++;
		}
	}
	vector<vector<int> > pref(n, vector<int> (q, 0));
	for(int start_diff = 1; start_diff <= n; start_diff++)
	{
		int cur_ans = 0;
		if(start_diff + l - 1 >= n)
		{
			continue;
		}
		for(int i = 0; i < l; i++)
		{
			cur_ans += (a[i] != a[i + start_diff]);
		}
		pref[0][idk[next_high[cur_ans]]]++;
		pref[start_diff][idk[next_high[cur_ans]]]++;
		//cout << "i = 0, start_diff = " << start_diff << ", cur_ans = " << cur_ans << "\n";
		for(int i = 1; i < n; i++)
		{
			int j = i + start_diff;
			if(j + l - 1 >= n)
			{
				continue;
			}
			cur_ans -= (a[i - 1] != a[j - 1]);
			cur_ans += (a[i + l - 1] != a[j + l - 1]);
			if(next_high[cur_ans] != -1) pref[i][idk[next_high[cur_ans]]]++;
			if(next_high[cur_ans] != -1) pref[j][idk[next_high[cur_ans]]]++;
			//cout << "i = " << i << ", start_diff = " << start_diff << ", cur_ans = " << cur_ans << "\n";
		}
	}
	//cout << "prefix values\n";
	for(int i = 0; i < n; i++)
	{
		for(int j = 1; j < q; j++)
		{
			pref[i][j] += pref[i][j - 1];
		}
		/*for(int j = 0; j < q; j++)
		{
			cout << pref[i][j] << " ";
		}
		cout << "\n";*/
	}
	sort(queries.begin(), queries.end(), cmp);
	//cout << "OUTPUT\n";
	vector<int> smug(q + 1);
	for(int i = 0; i < queries.size() - 1; i++)
	{
		smug[i] = idk[next_high[queries[i].first]];
	}
	for(int i = 0; i < queries.size() - 1; i++)
	{
		//cout << "hello" << "\n";
		//cout << "queries[i].first = " << queries[i].first << ", next_low[queries[i].first] = " << next_high[queries[i].first] << "\n";
		for(int j = 0; j < n - l + 1; j++)
		{
			//cout << "i = " << i << ", j = " << j << "\n";
			cout << pref[j][smug[i]] << " ";
		}
		cout << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) 
	{
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

lot.cpp: In function 'void Solve()':
lot.cpp:117:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i = 0; i < queries.size() - 1; i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~
lot.cpp:121:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(int i = 0; i < queries.size() - 1; i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~

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