Submission #199471

#	Time	Username	Problem	Language	Result	Execution time	Memory
199471		arnold518	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3088 ms	48228 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];
	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));
	}
};

struct MAXSEG
{
	int tree[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));
	}
};

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 %d\n", A[i], B[i]);

	SB.init(1, 1, N, B);
	for(i=1; i<=N; i++)
	{
		int lo=A[i]-1, hi=N;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(SB.query(1, 1, N, A[i], mid)>=i) hi=mid;
			else lo=mid;
		}
		L[i]=hi;
	}
	
	SA.init(1, 1, N, A);
	for(i=1; i<=N; i++)
	{
		int lo=1, hi=B[i]+1;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(SA.query(1, 1, N, mid, B[i])<=i) lo=mid;
			else hi=mid;
		}
		R[i]=lo;
	}

	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 MAXSEG::init(int, int, int, int*)':
long_mansion.cpp:42: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:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:93:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
long_mansion.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
long_mansion.cpp:61:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
long_mansion.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:64: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:120: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