oj.uz

Submission #125438

# Submission time Handle Problem Language Result Execution time Memory
125438 2019-07-05T10:06:39 Z onjo0127 Long Mansion (JOI17_long_mansion) C++11
100 / 100
 786 ms 112092 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

struct minseg {
	vector<int> T;
	void init(vector<int> &A, int idx, int s, int e) {
		if(s == e) {
			T[idx] = A[s];
			return;
		}
		int m = s+e >> 1;
		init(A, idx*2, s, m);
		init(A, idx*2+1, m+1, e);
		T[idx] = min(T[idx*2], T[idx*2+1]);
	}
	// 구간 [l, r]에서 v 이하이면서 가장 오른쪽에 있는 원소 위치 리턴
	int find(int idx, int s, int e, int l, int r, int v) {
		if(r < s || e < l || T[idx] > v) return -1;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = find(idx*2+1, m+1, e, l, r, v);
		if(tmp != -1) return tmp;
		return find(idx*2, s, m, l, r, v);
	}
	minseg(int sz) {
		T.resize(sz*4);
	}
};

struct maxseg {
	vector<int> T;
	void init(vector<int> &A, int idx, int s, int e) {
		if(s == e) {
			T[idx] = A[s];
			return;
		}
		int m = s+e >> 1;
		init(A, idx*2, s, m);
		init(A, idx*2+1, m+1, e);
		T[idx] = max(T[idx*2], T[idx*2+1]);
	}
	// 구간 [l, r]에서 v 이상이면서 가장 왼쪽에 있는 원소 위치 리턴
	int find(int idx, int s, int e, int l, int r, int v) {
		if(r < s || e < l || T[idx] < v) return -1;
		if(s == e) return s;
		int m = s+e >> 1;
		int tmp = find(idx*2, s, m, l, r, v);
		if(tmp != -1) return tmp;
		return find(idx*2+1, m+1, e, l, r, v);
	}
	maxseg(int sz) {
		T.resize(sz*4);
	}
};

int LM[500009], RM[500009];
int C[500009], B[500009], L[500009], R[500009], LE[500009], RE[500009];
vector<int> A[500009], P[500009];

int main() {
	int N; scanf("%d",&N);
	for(int i=1; i<N; i++) scanf("%d", &C[i]);
	for(int i=1; i<=N; i++) P[i].push_back(0);
	for(int i=1; i<=N; i++) {
		scanf("%d",&B[i]);
		for(int j=0; j<B[i]; j++) {
			int foo; scanf("%d",&foo);
			P[foo].push_back(i);
			A[i].push_back(foo);
		}
	}
	for(int i=1; i<=N; i++) P[i].push_back(N+1);
	R[0] = N+1; L[N] = 0;
	for(int i=1; i<N; i++) {
		L[i] = *(--upper_bound(P[C[i]].begin(), P[C[i]].end(), i));
		R[i] = *upper_bound(P[C[i]].begin(), P[C[i]].end(), i);
	}
	minseg LG(N+1); maxseg RG(N+1);
	vector<int> LS = {-1}, RS;
	for(int i=1; i<=N; i++) LS.push_back(L[i]);
	for(int i=0; i<N; i++) RS.push_back(R[i]);
	LG.init(LS, 1, 1, N); RG.init(RS, 1, 0, N-1);

	for(int i=0; i<N; i++) {
		int s = i+1, e = LG.find(1, 1, N, i+1, R[i]-1, i);
		// printf("LEFT INTERVAL: [%d, %d]\n", s, e);
		LE[s] = e;
	}
	for(int i=1; i<=N; i++) {
		int s = RG.find(1, 0, N-1, L[i], i-1, i+1) + 1, e = i;
		// printf("RIGHT INTERVAL: [%d, %d]\n", s, e);
		RE[e] = s;
	}

	for(int i=1; i<=N; i++) LM[i] = 0, RM[i] = N+1;

	priority_queue<pii> LPQ, RPQ;
	for(int i=1; i<=N; i++) {
		while(LPQ.size() && LPQ.top().second < i) LPQ.pop();
		if(LE[i] > 0) LPQ.push({i, LE[i]});
		if(LPQ.size()) LM[i] = LPQ.top().first;
	}
	for(int i=N; i>=1; i--) {
		while(RPQ.size() && i < RPQ.top().second) RPQ.pop();
		if(RE[i] > 0) RPQ.push({-i, RE[i]});
		if(RPQ.size()) RM[i] = -RPQ.top().first;
	}

	for(int i=1; i<=N; i++) {
		// printf("i: %d, LM: %d, RM: %d\n", i, LM[i], RM[i]);
	}

	int Q; scanf("%d",&Q);
	while(Q--) {
		int X, Y; scanf("%d%d",&X,&Y);
		if(LM[X] <= Y && Y <= RM[X]) puts("YES");
		else puts("NO");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In member function 'void minseg::init(std::vector<int>&, int, int, int)':
long_mansion.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
long_mansion.cpp: In member function 'int minseg::find(int, int, int, int, int, int)':
long_mansion.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
long_mansion.cpp: In member function 'void maxseg::init(std::vector<int>&, int, int, int)':
long_mansion.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
long_mansion.cpp: In member function 'int maxseg::find(int, int, int, int, int, int)':
long_mansion.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
long_mansion.cpp:64:30: 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:67: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:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int foo; scanf("%d",&foo);
             ~~~~~^~~~~~~~~~~
long_mansion.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q);
         ~~~~~^~~~~~~~~
long_mansion.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int X, Y; scanf("%d%d",&X,&Y);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 27 ms 24440 KB Output is correct
3 Correct 29 ms 24696 KB Output is correct
4 Correct 27 ms 24184 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24312 KB Output is correct
7 Correct 26 ms 24184 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 27 ms 24440 KB Output is correct
3 Correct 29 ms 24696 KB Output is correct
4 Correct 27 ms 24184 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24312 KB Output is correct
7 Correct 26 ms 24184 KB Output is correct
8 Correct 154 ms 29772 KB Output is correct
9 Correct 154 ms 29664 KB Output is correct
10 Correct 157 ms 30200 KB Output is correct
11 Correct 157 ms 30840 KB Output is correct
12 Correct 145 ms 29048 KB Output is correct
13 Correct 151 ms 30000 KB Output is correct
14 Correct 150 ms 29944 KB Output is correct
15 Correct 150 ms 30072 KB Output is correct
16 Correct 153 ms 29736 KB Output is correct
17 Correct 150 ms 29944 KB Output is correct
18 Correct 152 ms 30072 KB Output is correct
19 Correct 150 ms 30024 KB Output is correct
20 Correct 148 ms 29816 KB Output is correct
21 Correct 148 ms 29692 KB Output is correct
22 Correct 155 ms 29720 KB Output is correct
23 Correct 151 ms 29816 KB Output is correct
24 Correct 151 ms 29688 KB Output is correct
25 Correct 151 ms 29720 KB Output is correct
26 Correct 151 ms 29688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 47604 KB Output is correct
2 Correct 331 ms 47204 KB Output is correct
3 Correct 323 ms 47044 KB Output is correct
4 Correct 334 ms 47344 KB Output is correct
5 Correct 331 ms 47520 KB Output is correct
6 Correct 276 ms 45816 KB Output is correct
7 Correct 268 ms 45804 KB Output is correct
8 Correct 267 ms 45808 KB Output is correct
9 Correct 269 ms 45936 KB Output is correct
10 Correct 268 ms 46116 KB Output is correct
11 Correct 285 ms 46196 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 27 ms 24440 KB Output is correct
3 Correct 29 ms 24696 KB Output is correct
4 Correct 27 ms 24184 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24312 KB Output is correct
7 Correct 26 ms 24184 KB Output is correct
8 Correct 154 ms 29772 KB Output is correct
9 Correct 154 ms 29664 KB Output is correct
10 Correct 157 ms 30200 KB Output is correct
11 Correct 157 ms 30840 KB Output is correct
12 Correct 145 ms 29048 KB Output is correct
13 Correct 151 ms 30000 KB Output is correct
14 Correct 150 ms 29944 KB Output is correct
15 Correct 150 ms 30072 KB Output is correct
16 Correct 153 ms 29736 KB Output is correct
17 Correct 150 ms 29944 KB Output is correct
18 Correct 152 ms 30072 KB Output is correct
19 Correct 150 ms 30024 KB Output is correct
20 Correct 148 ms 29816 KB Output is correct
21 Correct 148 ms 29692 KB Output is correct
22 Correct 155 ms 29720 KB Output is correct
23 Correct 151 ms 29816 KB Output is correct
24 Correct 151 ms 29688 KB Output is correct
25 Correct 151 ms 29720 KB Output is correct
26 Correct 151 ms 29688 KB Output is correct
27 Correct 351 ms 47604 KB Output is correct
28 Correct 331 ms 47204 KB Output is correct
29 Correct 323 ms 47044 KB Output is correct
30 Correct 334 ms 47344 KB Output is correct
31 Correct 331 ms 47520 KB Output is correct
32 Correct 276 ms 45816 KB Output is correct
33 Correct 268 ms 45804 KB Output is correct
34 Correct 267 ms 45808 KB Output is correct
35 Correct 269 ms 45936 KB Output is correct
36 Correct 268 ms 46116 KB Output is correct
37 Correct 285 ms 46196 KB Output is correct
38 Correct 746 ms 97452 KB Output is correct
39 Correct 786 ms 112092 KB Output is correct
40 Correct 599 ms 81768 KB Output is correct
41 Correct 686 ms 101856 KB Output is correct
42 Correct 330 ms 46548 KB Output is correct
43 Correct 306 ms 45996 KB Output is correct
44 Correct 515 ms 61516 KB Output is correct
45 Correct 511 ms 61428 KB Output is correct
46 Correct 510 ms 61392 KB Output is correct
47 Correct 316 ms 44660 KB Output is correct
48 Correct 297 ms 45136 KB Output is correct
49 Correct 466 ms 62188 KB Output is correct
50 Correct 543 ms 61724 KB Output is correct
51 Correct 546 ms 61724 KB Output is correct
52 Correct 419 ms 61092 KB Output is correct
53 Correct 543 ms 78308 KB Output is correct
54 Correct 653 ms 92508 KB Output is correct
55 Correct 564 ms 77888 KB Output is correct