Submission #26403

#	Time	Username	Problem	Language	Result	Execution time	Memory
26403		pacu	Long Mansion (JOI17_long_mansion)	C++98	100 / 100	1106 ms	140540 KiB

long_mansion

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define MAXN 500005

int N,Q;
int len[MAXN];
vector<int> keys[MAXN];
int req[MAXN];	//req[i] is for i to i+1
int nearLeft[MAXN];
int nearRight[MAXN];
vector<int> lstLeft[MAXN];
vector<int> lstRight[MAXN];
int vRight[MAXN];
int vLeft[MAXN];

int occ[MAXN];

set<int> sLeft,sRight;
int l[MAXN],r[MAXN];

int main()
{
	scanf("%d",&N);
	for(int i=1;i<N;i++)
	{
		scanf("%d",&req[i]);
		req[i]--;
	}
	req[0] = req[N] = N;
	int a,b;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&len[i]);
		for(int j=0;j<len[i];j++)
		{
			scanf("%d",&a);
			a--;
			keys[i].push_back(a);
		}
	}
	for(int i=0;i<=N;i++)
		occ[i] = 0;
	nearLeft[0] = 0;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<len[i];j++)
			occ[keys[i][j]] = i;
		nearLeft[i] = occ[req[i]];
		lstLeft[nearLeft[i]].push_back(i);
	}
	for(int i=0;i<=N;i++)
		occ[i] = N+1;
	nearRight[N] = N+1;
	for(int i=N;i>0;i--)
	{
		for(int j=0;j<len[i];j++)
			occ[keys[i][j]] = i;
		nearRight[i-1] = occ[req[i-1]];
		lstRight[nearRight[i-1]].push_back(i-1);
	}
	set<int>::iterator it;
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<lstLeft[i].size();j++)
			sRight.insert(lstLeft[i][j]);
		it = sRight.lower_bound(nearRight[i]);
		it--;
		vRight[i] = *it;
	}
	for(int i=N+1;i>0;i--)
	{
		for(int j=0;j<lstRight[i].size();j++)
			sLeft.insert(lstRight[i][j]);
		it = sLeft.lower_bound(nearLeft[i-1]);
		vLeft[i-1] = *it;
	}
	vector<int> v;
	for(int i=1;i<=N;i++)
	{
		v.push_back(i);
		while(v.size()>0 && v.back() > vLeft[i])
		{
			r[v.back()] = i;
			v.pop_back();
		}
	}
	v.clear();
	for(int i=N-1;i>=0;i--)
	{
		v.push_back(i+1);
		while(v.size()>0 && v.back() <= vRight[i])
		{
			l[v.back()] = i+1;
			v.pop_back();
		}
	}
	int Q;
	scanf("%d",&Q);
	int x,y;
	for(int i=0;i<Q;i++)
	{
		scanf("%d %d",&x,&y);
		if(l[x] <= y && y <= r[x]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<lstLeft[i].size();j++)
                ^
long_mansion.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<lstRight[i].size();j++)
                ^
long_mansion.cpp:33:8: warning: unused variable 'b' [-Wunused-variable]
  int a,b;
        ^
long_mansion.cpp:26:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
long_mansion.cpp:29:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
                      ^
long_mansion.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&len[i]);
                      ^
long_mansion.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a);
                  ^
long_mansion.cpp:101:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
long_mansion.cpp:105:23: 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: 75 / 75