Submission #126237

#	Time	Username	Problem	Language	Result	Execution time	Memory
126237		briansu	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1110 ms	136236 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...)
#define endl '\n'
#endif

const ll MAXn = 5e5 + 5;
const ll INF = ll(1e17);
const ll MOD = 1000000007;

struct node{
	ll l, r;
	node *lc, *rc;
	ll mn;
	node(ll li,ll ri,node *lci = 0, node *rci = 0):l(li), r(ri), lc(lci), rc(rci), mn(INF){}
	void pull(){
		if(l != r-1)mn = min(lc->mn, rc->mn);
	}
	void ins(ll x,ll k)
	{
		if(l == r-1)mn = k;
		else if(x < (l + r) / 2)lc->ins(x, k), pull();
		else rc->ins(x, k), pull();
	}
	ll qr(ll li,ll ri)
	{
		if(li >= r || ri <= l)return INF;
		else if(li <= l && ri >= r)return mn;
		else return min(lc->qr(li, ri), rc->qr(li, ri));
	}
	ll fd(ll x)
	{
		if(l == r-1)return l;
		else if(lc->mn <= x)return lc->fd(x);
		else return rc->fd(x);
	}
};

node *build(ll l,ll r)
{
	if(l == r-1)return new node(l, r);
	else return new node(l, r, build(l, (l + r) / 2), build((l + r) / 2, r));
}

vector<ll> keys[MAXn];
vector<ii> qr[MAXn];
ll lk[MAXn], rk[MAXn], l[MAXn], r[MAXn], lst[MAXn], ans[MAXn];

int main(){
	IOS();
	ll n;
	cin>>n;
	REP1(i, n - 1)cin>>rk[i], lk[i + 1] = rk[i];
	REP1(i, n)
	{
		ll t;
		cin>>t;
		while(t--)
		{
			ll x;
			cin>>x;
			keys[i].pb(x);
		}
	}
	lk[1] = rk[n] = 1;
	REP1(i, n)lst[i] = 0;
	REP1(i, n)
	{
		l[i] = lst[lk[i]];
		for(ll t:keys[i])lst[t] = i;
	}
	REP1(i, n)lst[i] = n + 1;
	for(int i = n;i > 0;i --)
	{
		r[i] = lst[rk[i]];
		for(ll t:keys[i])lst[t] = i;
	}
	ll q;
	cin>>q;
	REP(i, q)
	{
		ll a, b;
		cin>>a>>b;
		qr[a].pb(ii(b, i));
	}
	node *rt = build(0, n + 3);
	REP1(i, n)rt->ins(i, l[i]);
	rt->ins(n + 1, 0);
	set<ll> st;
	st.insert(0);
	r[0] = n + 1;
	for(int i = 0;i <= n + 1;i ++)debug(i, l[i], r[i]);
	REP1(i, n)
	{
		rt->ins(i, INF);
		while(1)
		{
			ll t = *st.rbegin();
			debug(t, r[t], rt->qr(t + 1, r[t] + 1));
			if(rt->qr(t + 1, r[t] + 1) > t)st.erase(t);
			else break;
		}
		ll a = *st.rbegin();
		ll b = rt->fd(a);
		for(auto &p:qr[i])ans[p.Y] = (p.X > a && p.X < b);
		while(SZ(st) && r[*st.rbegin()] <= r[i])
		{
			debug(*st.rbegin());
			st.erase(*st.rbegin());
		}
		st.insert(i);
	}
	REP(i, q)cout<<(ans[i] ? "YES" : "NO")<<endl;

}

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