제출 #953650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953650		arashMLG	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	3024 ms	26448 KiB

long_mansion

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...)    69
#define debugArr(...)  69
#endif
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")

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

const int N = 5e5 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,q;
vector<int> vals[N];

bool check(int l,int r,int c) {
	if(vals[c].empty()) return false;
	if(vals[c].back() < l) return false;
	int x = *lower_bound(all(vals[c]),l);
	return x <= r;
}

int c[N];
int l[N],r[N];
int psl[N],psr[N];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	for(int i = 1; i < n ; i ++) cin>>c[i];
	for(int i = 1; i <= n ; i++) {
		int x; cin>>x;
		while(x--) {
			int y; cin>>y;
			vals[y].pb(i);
		}
	}
	// calc l
	for(int i = 1; i <= n ; i++) {
		l[i] = i;
		while(l[i] > 1) {
			if(check(l[i],i,c[l[i]-1])) {
				l[i] --;
				l[i] = min(l[i],l[l[i]]);
			} else {
				break;
			}
		}
		//debug(i,l[i]);
	}
	// calc r
	for(int i = n ; i >= 1; i--) {
		r[i] = i;
		while(r[i] < n) {
			if(check(i,r[i],c[r[i]])) {
				r[i] ++;
				r[i] = max(r[i],r[r[i]]);
			} else {
				break;
			}
		}
		//debug(i,r[i]);	
	}
	vector<int> ord(n);
	iota(all(ord),1);
	//shuffle(all(ord),rng);
	for(int i : ord) {
		while(true) {
			l[i] = min(l[i],l[l[i]]);
			r[i] = max(r[i],r[r[i]]);
			bool x = false,y= false;
			if(l[i] > 1) {
				x = check(l[i],r[i],c[l[i]-1]);
			}
			if(r[i] < n) {
				y = check(l[i],r[i],c[r[i]]);
			}
			if(x) {
				l[i] --;
				continue;	
			}
			if(y) {
				r[i] ++;
				continue;
			}
			break;
		}
		debug(i,l[i],r[i]);
	}
	/*for(int i = 2; i <= n ; i++) {
		psl[i] += psl[i-1];
		psr[i] += psr[i-1];
		if(l[i] <= i-1 || check(i,r[i],c[i-1])) {
			psl[i] ++;
			debug(i,"1");
		}
		if(r[i-1] >= i || check(l[i-1],i-1,c[i-1])) {
			psr[i] ++;
			debug(i,"2");
		}
	}*/
	cin>>q;
	while(q--) {
		int x,y; cin>>x>>y;
		cout<< (y <= r[x] && y >= l[x] ? "YES" : "NO") << '\n';
	}
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

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

long_mansion.cpp: In function 'int32_t main()':
long_mansion.cpp:5:23: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...)    69
      |                       ^~
long_mansion.cpp:106:3: note: in expansion of macro 'debug'
  106 |   debug(i,l[i],r[i]);
      |   ^~~~~

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