Submission #125438

#	Time	Username	Problem	Language	Result	Execution time	Memory
125438		onjo0127	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	786 ms	112092 KiB

long_mansion

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75