제출 #578496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578496		alireza_kaviani	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	431 ms	72192 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , q , B[MAXN] , C[MAXN] , last[MAXN] , prv[MAXN] , nxt[MAXN] , L[MAXN] , R[MAXN] , seg[MAXN << 2];
vector<int> A[MAXN];

void build(int id = 1 , int l = 1 , int r = n + 2){
	if(r - l == 1){
		seg[id] = prv[l];
		return;
	}
	int mid = l + r >> 1;
	build(lc , l , mid);
	build(rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

int Find(int ql , int qr , int x , int id = 1 , int l = 1 , int r = n + 2){
	if(qr <= l || r <= ql || seg[id] >= x)	return -1;
	if(r - l == 1)	return l;
	int mid = l + r >> 1;
	int res = Find(ql , qr , x , lc , l , mid);
	if(res != -1)	return res;
	return Find(ql , qr , x , rc , mid , r);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n;
	for(int i = 1 ; i < n ; i++)	cin >> C[i];
	for(int i = 1 ; i <= n ; i++){
		cin >> B[i];
		for(int j = 0 ; j < B[i] ; j++){
			int x;
			cin >> x;
			A[i].push_back(x);
		}
	}
	for(int i = 1 ; i <= n ; i++){
		prv[i] = last[C[i - 1]];
		for(int j : A[i]){
			last[j] = i;
		}
	}
	fill(last , last + MAXN , n + 1);
	for(int i = n ; i >= 1 ; i--){
		nxt[i] = last[C[i]];
		for(int j : A[i]){
			last[j] = i;
		}
	}
	nxt[0] = n + 1;
	build();
	for(int i = 1 ; i <= n ; i++){
		L[i] = R[i] = i;
		while(1){
			int newR = Find(R[i] + 1, n + 2, L[i]) - 1;
			int newL = (nxt[L[i] - 1] <= newR ? L[L[i] - 1] : L[i]);
			if(newL == L[i] && newR == R[i])	break;
			L[i] = newL;
			R[i] = newR;
		}
	}
	cin >> q;
	while(q--){
		int x , y;
		cin >> x >> y;
		if(L[x] <= y && y <= R[x]){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}
	}

    return 0;
}
/*

*/

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

long_mansion.cpp: In function 'void build(int, int, int)':
long_mansion.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid = l + r >> 1;
      |            ~~^~~
long_mansion.cpp: In function 'int Find(int, int, int, int, int, int)':
long_mansion.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid = l + r >> 1;
      |            ~~^~~

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