oj.uz

Submission #70991

# Submission time Handle Problem Language Result Execution time Memory
70991 2018-08-24T01:28:33 Z 윤교준(#2204) Lottery (CEOI18_lot) C++11
0 / 100
 790 ms 4708 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 10005;
const int MAXQ = 105;

int D[MAXN];
int A[MAXN];
int B[MAXQ];

int Ans[MAXN][MAXQ];
int N, L, Q;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> L;
	for(int i = 1; i <= N; i++) cin >> A[i];
	cin >> Q;
	for(int i = 1; i <= Q; i++) cin >> B[i];

	{
		vector<int> V;
		for(int i = 1; i <= Q; i++) V.eb(B[i]);
		sorv(V); univ(V);

		for(int i = 0; i <= V[0]; i++) D[i] = 1;
		for(int i = 1; i < sz(V); i++) {
			for(int j = V[i-1]+1; j <= V[i]; j++)
				D[j] = i+1;
		}
	}

	{
		vector<int> C(N+5, 0);

		for(int l = 1; l <= N-L; l++) {
			for(int i = 1; i <= N; i++) C[i] = 0;
			for(int s = 1, e = 1+l; e <= N; s++, e++) {
				C[s] = (A[s] == A[e] ? 0 : 1);
			}
			for(int i = 1; i <= N; i++) C[i] += C[i-1];
			for(int s = 1, e = 1+l; e+L-1 <= N; s++, e++) {
				int t = C[s+L-1] - C[s-1];
				Ans[s][D[t]]++;
				Ans[e][D[t]]++;
			}
		}
	}

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= Q; j++)
			Ans[i][j] += Ans[i][j-1];
	}

	for(int i = 1; i <= Q; i++) {
		for(int j = 1; j <= N-L+1; j++)
			printf("%d ", Ans[j][D[B[i]]]);
		puts("");
	}
	return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 790 ms 4708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 790 ms 4708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -