Submission #261785

#	Time	Username	Problem	Language	Result	Execution time	Memory
261785		arnold518	Lottery (CEOI18_lot)	C++14	100 / 100	2013 ms	8580 KiB

lot

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;
const int MAXQ = 100;

int N, L, Q, A[MAXN+10];
int B[MAXQ+10];
int C[MAXN+10];
int pos[MAXN+10];

int ans[MAXQ+10][MAXN+10];

int main()
{
	scanf("%d%d", &N, &L);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
	scanf("%d", &Q);
	vector<int> V;
	for(int i=1; i<=Q; i++)
	{
		scanf("%d", &B[i]);
		B[i]=L-B[i];
		V.push_back(B[i]);
	}
	V.push_back(0);
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for(int i=0; i<=L; i++) pos[i]=upper_bound(V.begin(), V.end(), i)-V.begin();

	for(int i=1-N; i<N; i++)
	{
		if(i==0) continue;
		for(int j=1; j<=N-L+1; j++) C[j]=0;
		for(int j=max(1, 1-i); j<=min(N, N-i); j++)
		{
			int p=j, q=j+i;
			if(A[p]!=A[q]) continue;
			int lp=max(1, p-L+1), rp=min(N-L+1, p);
			int lq=max(1, q-L+1), rq=min(N-L+1, q);
			lp=max(lp, lq-i); rp=min(rp, rq-i);
			if(lp>rp) continue;
			lq=lp+i; rq=rp+i;
			C[lp]++; C[rp+1]--;
		}
		for(int j=max(1, 1-i); j<=min(N-L+1, N-L+1-i); j++) C[j]+=C[j-1];
		for(int j=max(1, 1-i); j<=min(N-L+1, N-L+1-i); j++) ans[pos[C[j]]][j]++;
	}
	

	for(int i=V.size(); i>=0; i--) for(int j=1; j<=N-L+1; j++) ans[i][j]+=ans[i+1][j];

	for(int i=1; i<=Q; i++)
	{
		for(int j=1; j<=N-L+1; j++) printf("%d ", ans[pos[B[i]]][j]); printf("\n");
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:59:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int j=1; j<=N-L+1; j++) printf("%d ", ans[pos[B[i]]][j]); printf("\n");
   ^~~
lot.cpp:59:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int j=1; j<=N-L+1; j++) printf("%d ", ans[pos[B[i]]][j]); printf("\n");
                                                                 ^~~~~~
lot.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
                          ~~~~~^~~~~~~~~~~~~
lot.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
lot.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &B[i]);
   ~~~~~^~~~~~~~~~~~~

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