제출 #218498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218498		patrikpavic2	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	664 ms	50432 KiB

long_mansion

#include <cstdio>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 5e5 + 500;

int c[N], L[N], R[N], ima[N], tL[N], tR[N], C[N];
vector < int > mogu[N];

inline void clean(int l,int r){
	for(int i = l;i < r;i++){
		for(int x : mogu[i])
			ima[x] = 0;
	}
}

inline void ubaci(int i){
	for(int x : mogu[i])
		ima[x] = 1;
}

inline void siri(int l,int r, int &cL, int &cR){
	for(;;){
		if(cL > l && ima[C[cL - 1]]){
			cL--; 
			if(cL != l) 
				ubaci(cL - 1);
			continue;
		}
		if(cR < r && ima[C[cR + 1]]){
			cR++;
			if(cR != r) 
				ubaci(cR);
			continue;
		}
		break;
	}
}


void rijesi(int l,int r){
	if(l == r) return;
	//printf("l = %d r = %d\n", l, r);
	if(l + 1 == r){
		ubaci(l);
		L[l] = r, R[l] = l;
		if(ima[C[l]]) 
			L[l] = l;
		if(ima[C[r]]) 
			R[l] = r;
		clean(l, r);
		//printf("L[ %d ] = %d , R[ %d ] = %d\n", 3, L[3], 3, R[3]);
		return;
	}
	int mid = (l + r) / 2;
	rijesi(l, mid); rijesi(mid, r);
	int cL = mid, cR = mid - 1;
	if(mid - 1 >= l)
		ubaci(mid - 1);
	for(int ll = mid - 1;ll >= l;ll--){
		if(cL > ll + 1){
			ubaci(ll); cL = ll + 1;
		}
		siri(l, r, cL, cR);		
		tL[ll] = cL, tR[ll] = cR;
	}
	clean(l, r);
	cL = mid + 1, cR = mid;
	ubaci(mid);
	for(int rr = mid;rr < r;rr++){
		if(cR <= rr){
			ubaci(rr); cR = rr;
		}
		siri(l, r, cL, cR);
		tL[rr] = cL, tR[rr] = cR;
	//	printf("cL = %d cR = %d\n", cL, cR);
	}
	//printf("(%d %d)  L[ %d ] = %d , R[ %d ] = %d\n", l, r, 3, tL[3], 3, tR[3]);
	clean(l, r);
	for(int i = l;i < mid;i++){
		if(R[i] == mid)
			L[i] = tL[max(L[i] - 1, l)], R[i] = tR[max(L[i] - 1, l)];
	}
	for(int i = mid;i < r;i++){
		if(L[i] == mid)
			L[i] = tL[min(R[i], r - 1)], R[i] = tR[min(R[i], r - 1)];
	}
	//printf("(%d %d)  L[ %d ] = %d , R[ %d ] = %d\n", l, r, 3, L[3], 3, R[3]);
	return;
}

int n, q;

int main(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++)
		scanf("%d", C + i);
	for(int i = 0;i < n;i++){
		int kol; scanf("%d", &kol);
		for(;kol--;){
			int x; scanf("%d", &x);
			mogu[i].PB(x);
		}
	}
	//for(int i = 0;i <= n;i++){
	//	printf("%d == ", C[i]);
	//	if(i != n){
	//		printf("[ ");
	//		for(int x : mogu[i]) printf("%d ", x);
	//		printf("] == ");
	//	}
	//}
	//printf("\n");
	rijesi(0, n);
	//for(int i = 0;i < n;i++){
	//	printf("i = %d interval %d %d\n", i, L[i] - 1, R[i]);
	//}
	scanf("%d", &q);
	for(;q--;){
		int x, y; scanf("%d%d", &x, &y); x--, y--;
		printf((L[x] - 1 <= y && y <= R[x]) ? "YES\n" : "NO\n");
	}
}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:104:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int kol; scanf("%d", &kol);
            ~~~~~^~~~~~~~~~~~
long_mansion.cpp:106:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~
long_mansion.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:125: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); x--, y--;
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75