제출 #821422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821422		AdamGS	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1440 ms	142720 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
vector<int>V[LIM];
map<pair<int,int>,pair<int,int>>mp;
pair<int,int>P[LIM];
int T[LIM], kto[LIM], trlewo[4*LIM], trprawo[4*LIM], N=1, n;
int cntprawo(int l, int r) {
	l+=N; r+=N;
	int ans=max(trprawo[l], trprawo[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, trprawo[l+1]);
		if(r%2==1) ans=max(ans, trprawo[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
int cntlewo(int l, int r) {
	l+=N; r+=N;
	int ans=min(trlewo[l], trlewo[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=min(ans, trlewo[l+1]);
		if(r%2==1) ans=min(ans, trlewo[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
pair<int,int>solve(pair<int,int>x) {
	if(mp.find(x)!=mp.end()) return mp[x];
	int po=0, ko=x.st-1;
	pair<int,int>nxt=x;
	if(x.st && cntprawo(x.st-1, x.st-1)<=x.nd) {
		int po=0, ko=x.st-1;
		while(po<ko) {
			int sr=(po+ko)/2;
			if(cntprawo(sr, x.st-1)<=x.nd) ko=sr; else po=sr+1;
		}
		nxt.st=po;
	}
	if(x.nd<n-1 && cntlewo(x.nd+1, x.nd+1)>=x.st) {
		int po=x.nd+1, ko=n-1;
		while(po<ko) {
			int sr=(po+ko+1)/2;
			if(cntlewo(x.nd+1, sr)>=x.st) po=sr; else ko=sr-1;
		}
		nxt.nd=ko;
	}
	if(nxt==x) return mp[x]=nxt;
	return mp[x]=solve(nxt);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	while(N<n) N*=2;
	rep(i, n-1) {
		cin >> T[i]; --T[i];
	}
	rep(i, n) {
		int k;
		cin >> k;
		while(k--) {
			int a;
			cin >> a; --a;
			V[i].pb(a);
		}
	}
	rep(i, n) kto[i]=-1;
	rep(i, n) {
		for(auto j : V[i]) kto[j]=i;
		if(i<n-1) trlewo[N+i+1]=kto[T[i]];
	}
	rep(i, n) kto[i]=n;
	for(int i=n-1; i>=0; --i) {
		for(auto j : V[i]) kto[j]=i;
		if(i) trprawo[N+i-1]=kto[T[i-1]];
	}
	for(int i=N-1; i; --i) {
		trlewo[i]=min(trlewo[2*i], trlewo[2*i+1]);
		trprawo[i]=max(trprawo[2*i], trprawo[2*i+1]);
	}
	rep(i, n) P[i]=solve({i, i});
	int q;
	cin >> q;
	while(q--) {
		int a, b;
		cin >> a >> b; --a; --b;
		cout << (P[a].st<=b&&b<=P[a].nd?"YES":"NO") << '\n';
	}
}

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

long_mansion.cpp: In function 'std::pair<int, int> solve(std::pair<int, int>)':
long_mansion.cpp:36:6: warning: unused variable 'po' [-Wunused-variable]
   36 |  int po=0, ko=x.st-1;
      |      ^~
long_mansion.cpp:36:12: warning: unused variable 'ko' [-Wunused-variable]
   36 |  int po=0, ko=x.st-1;
      |            ^~

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