Submission #650498

#	Time	Username	Problem	Language	Result	Execution time	Memory
650498		fatemetmhr	Lottery (CEOI18_lot)	C++17	100 / 100	675 ms	8288 KiB

lot

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e4   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

vector <pair<int, int>> qu;
int a[maxn5], have[maxn5], reff[maxn5], ind[103];
int ans[102][maxn5];

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n, l; cin >> n >> l;
	for(int i = 0; i < n; i++) cin >> a[i];
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int k; cin >> k;
		qu.pb({k, i});
	}
	sort(all(qu));
	if(qu.back().fi < l) qu.pb({l, q});
	for(int i = 0; i <= l; i++){
		reff[i] = lower_bound(all(qu), mp(i, -1)) - qu.begin();
	}
	
	
	for(int i = 1; i < n; i++){
		fill(have, have + n + 2, 0);
		for(int j = 0; j + i < n; j++) if(a[j] != a[j + i]){
			have[max(0, j - l + 1)]++;
			have[j + 1]--;
		}
		int now = 0;
		for(int j = 0; j + i + l - 1 < n; j++){
			now += have[j];
			ans[reff[now]][j]++;
			ans[reff[now]][j + i]++;
		}	
	}
	
	ind[qu[0].se] = 0;
	for(int i = 1; i < qu.size(); i++){
		for(int j = 0; j < n; j++)
			ans[i][j] += ans[i - 1][j];
		ind[qu[i].se] = i;
		
	}
	for(int i = 0; i < q; i++){
		for(int j = 0; j + l - 1 < n; j++) cout << ans[ind[i]][j] << ' ';
		cout << '\n';
	}
}

Compilation message (stderr)

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

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