oj.uz

Submission #125304

# Submission time Handle Problem Language Result Execution time Memory
125304 2019-07-05T05:09:57 Z 임유진(#3061) Long Mansion (JOI17_long_mansion) C++14
15 / 100
 388 ms 39544 KB 
#include <stdio.h>
#include<vector>

using namespace std;

#define MAXN 100005
#define MAXQ 500005
#define MAXC 21

vector<int> A[MAXN];
int B[MAXN], C[MAXN];
int X[MAXQ], Y[MAXQ];
int L[MAXN], R[MAXN];
int ksum[MAXN][MAXC];
int ldoor[MAXN][MAXC], rdoor[MAXN][MAXC];

int main() {
	int N, Q;

	scanf("%d", &N);
	for(int i = 1; i < N; i++) scanf("%d", C + i);
	for(int i = 1; i <= N; i++) {
		scanf("%d", B + i);
		int t;
		for(int j = 0; j < B[i]; j++) {
			scanf("%d", &t);
			A[i].push_back(t);
		}
	}
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j < MAXC; j++) ksum[i][j] = ksum[i - 1][j];
		for(auto a : A[i]) ksum[i][a]++;
	}

	for(int i = 1; i < MAXC; i++) ldoor[1][i] = -1;
	for(int i = 2; i <= N; i++) {
		for(int j = 1; j < MAXC; j++) ldoor[i][j] = ldoor[i - 1][j];
		ldoor[i][C[i - 1]] = i - 1;
	}
	for(int i = 1; i < MAXC; i++) rdoor[N][i] = N;
	for(int i = N - 1; i > 0; i--) {
		for(int j = 1; j < MAXC; j++) rdoor[i][j] = rdoor[i + 1][j];
		rdoor[i][C[i]] = i;
	}

	/*
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= 5; j++) printf("(%d, %d)", ldoor[i][j], rdoor[i][j]);
		printf("\n");
	}
	*/

	for(int i = 1; i <= N; i++) {
		L[i] = R[i] = i;
		for(int j = 0; j < MAXC; j++) {
			int l = 1, r = N;
			for(int k = 1; k < MAXC; k++) if(ksum[R[i]][k] == ksum[L[i] - 1][k]) {
				l = max(l, ldoor[i][k] + 1);
				r = min(r, rdoor[i][k]);
				//printf("i = %d, k = %d, L = %d, R = %d, l = %d, r = %d\n", i, k, L[i], R[i], l, r);
			}
			L[i] = l;
			R[i] = r;
		}
	}

	//for(int i = 1; i <= N; i++) printf("L = %d, R = %d\n", L[i], R[i]);

	for(int i = 0; i < Q; i++) {
		if(L[X[i]] <= Y[i] && Y[i] <= R[X[i]]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:21:34: 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", C + i);
                             ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", B + i);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3448 KB Output is correct
2 Correct 10 ms 3704 KB Output is correct
3 Correct 12 ms 4344 KB Output is correct
4 Incorrect 9 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3448 KB Output is correct
2 Correct 10 ms 3704 KB Output is correct
3 Correct 12 ms 4344 KB Output is correct
4 Incorrect 9 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 38936 KB Output is correct
2 Correct 385 ms 39544 KB Output is correct
3 Correct 365 ms 39460 KB Output is correct
4 Correct 388 ms 39540 KB Output is correct
5 Correct 384 ms 39416 KB Output is correct
6 Correct 338 ms 38992 KB Output is correct
7 Correct 345 ms 39236 KB Output is correct
8 Correct 347 ms 39236 KB Output is correct
9 Correct 345 ms 39192 KB Output is correct
10 Correct 347 ms 39268 KB Output is correct
11 Correct 347 ms 39164 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3448 KB Output is correct
2 Correct 10 ms 3704 KB Output is correct
3 Correct 12 ms 4344 KB Output is correct
4 Incorrect 9 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -