Submission #319401

#	Time	Username	Problem	Language	Result	Execution time	Memory
319401		arnold518	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1573 ms	70080 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));
	}
	int query2(int node, int tl, int tr, int l, int r, int p)
	{
		if(r<tl || tr<l) return -1;
		if(tree[node]<=p) return -1;
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		int t=query2(node*2, tl, mid, l, r, p);
		if(t!=-1) return t;
		t=query2(node*2+1, mid+1, tr, l, r, p);
		if(t!=-1) return t;
		return -1;
	}
}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));
	}
	int query2(int node, int tl, int tr, int l, int r, int p)
	{
		if(r<tl || tr<l) return -1;
		if(tree[node]>=p) return -1;
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		int t=query2(node*2+1, mid+1, tr, l, r, p);
		if(t!=-1) return t;
		t=query2(node*2, tl, mid, l, r, p);
		if(t!=-1) return t;
		return -1;
	}
}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
		{
			P[i]=seg1.query2(1, 1, N, L[i]+1, i, i);
		}
		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
		{
			Q[i]=seg2.query2(1, 1, N, i, R[i-1]-1, i);
		}
		seg4.update(1, 1, N, i-1, Q[i]);
	}

	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 'int SEG1::query2(int, int, int, int, int, int)':
long_mansion.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'void SEG2::update(int, int, int, int, int)':
long_mansion.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'int SEG2::query1(int, int, int, int, int)':
long_mansion.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In member function 'int SEG2::query2(int, int, int, int, int, int)':
long_mansion.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid=tl+tr>>1;
      |           ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:93:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  for(int i=1; i<N; i++) scanf("%d", &C[i]);
      |                         ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |    scanf("%d", &p);
      |    ~~~~~^~~~~~~~~~
long_mansion.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |  scanf("%d", &QQ);
      |  ~~~~~^~~~~~~~~~~
long_mansion.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

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