Submission #319396

#	Time	Username	Problem	Language	Result	Execution time	Memory
319396		arnold518	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3051 ms	55280 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, QQ;
int C[MAXN+10];
vector<int> A[MAXN+10];

int L[MAXN+10], R[MAXN+10];
int P[MAXN+10], Q[MAXN+10];

struct SEG1
{
	int tree[MAXN*4+10];
	void update(int node, int tl, int tr, int p, int v)
	{
		if(tl==tr)
		{
			tree[node]=v;
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p, v);
		else update(node*2+1, mid+1, tr, p, v);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query1(int node, int tl, int tr, int l, int r)
	{
		int mid=tl+tr>>1;
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return -INF;
		return max(query1(node*2, tl, mid, l, r), query1(node*2+1, mid+1, tr, l, r));
	}
}seg1, seg4;

struct SEG2
{
	int tree[MAXN*4+10];
	void update(int node, int tl, int tr, int p, int v)
	{
		if(tl==tr)
		{
			tree[node]=v;
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p, v);
		else update(node*2+1, mid+1, tr, p, v);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	int query1(int node, int tl, int tr, int l, int r)
	{
		int mid=tl+tr>>1;
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return INF;
		return min(query1(node*2, tl, mid, l, r), query1(node*2+1, mid+1, tr, l, r));
	}
}seg2, seg3;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++) scanf("%d", &C[i]);
	for(int i=1; i<=N; i++) A[i].push_back(0);
	for(int i=1; i<=N; i++)
	{
		int t;
		scanf("%d", &t);
		while(t--)
		{
			int p;
			scanf("%d", &p);
			A[p].push_back(i);
		}
	}
	for(int i=1; i<=N; i++) A[i].push_back(N+1);

	for(int i=1; i<N; i++)
	{
		int col=C[i];
		L[i]=*(--upper_bound(A[col].begin(), A[col].end(), i));
		R[i]=*lower_bound(A[col].begin(), A[col].end(), i+1);
	}

	L[0]=0; R[0]=N+1;
	L[N]=0; R[N]=N+1;

	for(int i=1; i<=N; i++)
	{
		seg1.update(1, 1, N, i, R[i-1]);
	}

	for(int i=1; i<N; i++)
	{
		if(seg1.query1(1, 1, N, L[i]+1, i)<=i)
		{
			P[i]=N+1;
		}
		else
		{
			int lo=L[i], hi=i;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(seg1.query1(1, 1, N, L[i]+1, mid)>i) hi=mid;
				else lo=mid;
			}
			P[i]=hi;
		}
		seg3.update(1, 1, N, i, P[i]);
	}

	for(int i=1; i<N; i++)
	{
		seg2.update(1, 1, N, i, L[i]);
	}

	for(int i=2; i<=N; i++)
	{
		if(seg2.query1(1, 1, N, i, R[i-1]-1)>=i)
		{
			Q[i]=0;
		}
		else
		{
			int lo=i, hi=R[i-1];
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(seg2.query1(1, 1, N, mid, R[i-1]-1)<i) lo=mid;
				else hi=mid;
			}
			Q[i]=lo;
		}
		seg4.update(1, 1, N, i-1, Q[i]);
	}

	//for(int i=1; i<N; i++) printf("%d ", L[i]); printf(" : L\n");
	//for(int i=1; i<N; i++) printf("%d ", R[i]); printf(" : R\n");
	//for(int i=1; i<N; i++) printf("%d ", P[i]); printf(" : P\n");
	//for(int i=2; i<=N; i++) printf("%d ", Q[i]); printf(" : Q\n");

	scanf("%d", &QQ);
	while(QQ--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(x<y)
		{
			if(seg3.query1(1, 1, N, x, y-1)<=x) printf("NO\n");
			else printf("YES\n");
		}
		else
		{
			if(seg4.query1(1, 1, N, y, x-1)>=x) printf("NO\n");
			else printf("YES\n");
		}
	}
}

Compilation message (stderr)

long_mansion.cpp: In member function 'void SEG1::update(int, int, int, int, int)':
long_mansion.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'int SEG1::query1(int, int, int, int, int)':
long_mansion.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'void SEG2::update(int, int, int, int, int)':
long_mansion.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'int SEG2::query1(int, int, int, int, int)':
long_mansion.cpp:59:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:110:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |     int mid=lo+hi>>1;
      |             ~~^~~
long_mansion.cpp:135:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |     int mid=lo+hi>>1;
      |             ~~^~~
long_mansion.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:69:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  for(int i=1; i<N; i++) scanf("%d", &C[i]);
      |                         ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |    scanf("%d", &p);
      |    ~~~~~^~~~~~~~~~
long_mansion.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |  scanf("%d", &QQ);
      |  ~~~~~^~~~~~~~~~~
long_mansion.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  153 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

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