Submission #1215975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215975		Nika533	Lottery (CEOI18_lot)	C++20	100 / 100	575 ms	12580 KiB

lot

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=10005,QQ=105;
int n,m,T,k,l,val[N],q[QQ],ne[N],ans[N][QQ],anss[N][QQ];
void test_case() {
	cin>>n>>l;
	int arr[n+1];
	for (int i=1; i<=n; i++) {
		cin>>arr[i];
	}
	int Q; cin>>Q;
	pii qq[Q+1];
	for (int i=1; i<=Q; i++) {
		cin>>q[i]; qq[i]={q[i],i};
	}
	sort(qq+1,qq+Q+1);
	for (int i=l; i>=0; i--) {
		ne[i]=Q+1;
	}
	for (int j=1; j<=Q; j++) {
		if (ne[qq[j].f]==Q+1) ne[qq[j].f]=j;
	}
	ne[l+1]=0;
	for (int i=l; i>=0; i--) {
		if (ne[i]==Q+1) ne[i]=ne[i+1];
	}
	for (int dif=1; dif<=n-l; dif++) {
		int val=l;
		for (int i=1; i<=n-l+1; i++) {
			int j=i+dif;
			if (j>n-l+1) continue;
			if (i==1) {
				for (int o=0; o<l; o++) {
					if (arr[i+o]==arr[j+o]) {
						val--;
					}
				}
				ans[i][ne[val]]++; ans[j][ne[val]]++;
				continue;
			}
			if (arr[i-1]==arr[j-1]) val++;
			if (arr[i+l-1]==arr[j+l-1]) val--;
			ans[i][ne[val]]++; ans[j][ne[val]]++;
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=Q; j++) {
			if (j>1) ans[i][j]+=ans[i][j-1];
			anss[i][qq[j].s]=ans[i][j];
		}
	}
	for (int i=1; i<=Q; i++) {
		for (int j=1; j<=n-l+1; j++) {
			cout<<anss[j][i]<<" ";
		}
		cout<<endl;
	}
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message (stderr)

lot.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
lot.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main () {
      | ^~~~

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