Submission #199476

#	Time	Username	Problem	Language	Result	Execution time	Memory
199476		arnold518	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	1139 ms	144224 KiB

long_mansion

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

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

const int MAXN = 5e5;
const int INF = 987654321;

int N, Q, C[MAXN+10], A[MAXN+10], B[MAXN+10], L[MAXN+10], R[MAXN+10];
vector<int> V[MAXN+10];

struct MINSEG
{
	int tree[MAXN*4+10], val[MAXN*4+10];
	MINSEG() {}
	void init(int node, int tl, int tr, int *S)
	{
		if(tl==tr) { tree[node]=S[tl]; return; }
		int mid=tl+tr>>1;
		init(node*2, tl, mid, S);
		init(node*2+1, mid+1, tr, S);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return INF;
		int mid=tl+tr>>1;
		return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
	void query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) { val[node]=tree[node]; return; }
		if(r<tl || tr<l) { val[node]=INF; return; }
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r);
		query2(node*2+1, mid+1, tr, l, r);
		val[node]=min(val[node*2], val[node*2+1]);
	}
	int query3(int node, int tl, int tr, int l, int r, int k)
	{
		if(l<=tl && tr<=r) { val[node*2]=tree[node*2]; val[node*2+1]=tree[node*2+1]; }
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(val[node*2+1]<=k) return query3(node*2+1, mid+1, tr, l, r, k);
		else return query3(node*2, tl, mid, l, r, k);
	}
};

struct MAXSEG
{
	int tree[MAXN*4+10], val[MAXN*4+10];
	MAXSEG() {}
	void init(int node, int tl, int tr, int *S)
	{
		if(tl==tr) { tree[node]=S[tl]; return; }
		int mid=tl+tr>>1;
		init(node*2, tl, mid, S);
		init(node*2+1, mid+1, tr, S);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return -INF;
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
	void query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) { val[node]=tree[node]; return; }
		if(r<tl || tr<l) { val[node]=-INF; return; }
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r);
		query2(node*2+1, mid+1, tr, l, r);
		val[node]=max(val[node*2], val[node*2+1]);
	}
	int query3(int node, int tl, int tr, int l, int r, int k)
	{
		if(l<=tl && tr<=r) { val[node*2]=tree[node*2]; val[node*2+1]=tree[node*2+1]; }
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(val[node*2]>=k) return query3(node*2, tl, mid, l, r, k);
		else return query3(node*2+1, mid+1, tr, l, r, k);
	}
};

MINSEG SA, SL;
MAXSEG SB, SR;

int main()
{
	int i, j;

	scanf("%d", &N);
	for(i=1; i<N; i++) scanf("%d", &C[i]);
	for(i=1; i<=N; i++) V[i].push_back(0);
	for(i=1; i<=N; i++)
	{
		int t;
		scanf("%d", &t);
		while(t--)
		{
			int p;
			scanf("%d", &p);
			V[p].push_back(i);
		}
	}
	for(i=1; i<=N; i++) V[i].push_back(N+1);
	for(i=1; i<N; i++)
	{
		auto it=upper_bound(V[C[i]].begin(), V[C[i]].end(), i);
		B[i+1]=*it-1;
		A[i]=*(--it)+1;
	}
	A[N]=1; B[1]=N;

	//for(i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
	//for(i=1; i<=N; i++) printf("%d ", B[i]); printf("\n");

	SB.init(1, 1, N, B);
	for(i=1; i<=N; i++)
	{
		SB.query2(1, 1, N, A[i], N);
		L[i]=SB.query3(1, 1, N, A[i], N, i);
		//printf("%d %d %d : %d\n", A[i], N, i, L[i]);
	}

	SA.init(1, 1, N, A);
	for(i=1; i<=N; i++)
	{
		SA.query2(1, 1, N, 1, B[i]);
		R[i]=SA.query3(1, 1, N, 1, B[i], i);
	}

	SR.init(1, 1, N, R);
	SL.init(1, 1, N, L);

	scanf("%d", &Q);
	while(Q--)
	{
		int X, Y;
		scanf("%d%d", &X, &Y);

		if(X<Y)
		{
			if(SL.query(1, 1, N, X, Y-1)<=X) printf("NO\n");
			else printf("YES\n");
		}
		else
		{
			if(SR.query(1, 1, N, Y+1, X)>=X) printf("NO\n");
			else printf("YES\n");
		}
	}
}

Compilation message (stderr)

long_mansion.cpp: In member function 'void MINSEG::init(int, int, int, int*)':
long_mansion.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MINSEG::query(int, int, int, int, int)':
long_mansion.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'void MINSEG::query2(int, int, int, int, int)':
long_mansion.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MINSEG::query3(int, int, int, int, int, int)':
long_mansion.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'void MAXSEG::init(int, int, int, int*)':
long_mansion.cpp:59:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MAXSEG::query(int, int, int, int, int)':
long_mansion.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'void MAXSEG::query2(int, int, int, int, int)':
long_mansion.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MAXSEG::query3(int, int, int, int, int, int)':
long_mansion.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:95:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
long_mansion.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:98:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<N; i++) scanf("%d", &C[i]);
                     ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &X, &Y);
   ~~~~~^~~~~~~~~~~~~~~~

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