oj.uz

Submission #199471

# Submission time Handle Problem Language Result Execution time Memory
199471 2020-02-01T13:39:47 Z arnold518 Long Mansion (JOI17_long_mansion) C++14
25 / 100
 3000 ms 48228 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12412 KB Output is correct
2 Correct 25 ms 12536 KB Output is correct
3 Correct 35 ms 12796 KB Output is correct
4 Correct 22 ms 12408 KB Output is correct
5 Correct 21 ms 12408 KB Output is correct
6 Correct 22 ms 12408 KB Output is correct
7 Correct 20 ms 12408 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12412 KB Output is correct
2 Correct 25 ms 12536 KB Output is correct
3 Correct 35 ms 12796 KB Output is correct
4 Correct 22 ms 12408 KB Output is correct
5 Correct 21 ms 12408 KB Output is correct
6 Correct 22 ms 12408 KB Output is correct
7 Correct 20 ms 12408 KB Output is correct
8 Correct 297 ms 18256 KB Output is correct
9 Correct 295 ms 18296 KB Output is correct
10 Correct 319 ms 18680 KB Output is correct
11 Correct 328 ms 19320 KB Output is correct
12 Correct 290 ms 17784 KB Output is correct
13 Correct 259 ms 18424 KB Output is correct
14 Correct 257 ms 18552 KB Output is correct
15 Correct 256 ms 18424 KB Output is correct
16 Correct 240 ms 18168 KB Output is correct
17 Correct 256 ms 18424 KB Output is correct
18 Correct 254 ms 18552 KB Output is correct
19 Correct 263 ms 18424 KB Output is correct
20 Correct 251 ms 18464 KB Output is correct
21 Correct 261 ms 18424 KB Output is correct
22 Correct 258 ms 18552 KB Output is correct
23 Correct 242 ms 18296 KB Output is correct
24 Correct 246 ms 18276 KB Output is correct
25 Correct 242 ms 18168 KB Output is correct
26 Correct 241 ms 18168 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1068 ms 32664 KB Output is correct
2 Correct 998 ms 32352 KB Output is correct
3 Correct 1000 ms 31936 KB Output is correct
4 Correct 1016 ms 32632 KB Output is correct
5 Correct 993 ms 32372 KB Output is correct
6 Correct 900 ms 30872 KB Output is correct
7 Correct 900 ms 30712 KB Output is correct
8 Correct 878 ms 30688 KB Output is correct
9 Correct 914 ms 30584 KB Output is correct
10 Correct 901 ms 30776 KB Output is correct
11 Correct 910 ms 30596 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12412 KB Output is correct
2 Correct 25 ms 12536 KB Output is correct
3 Correct 35 ms 12796 KB Output is correct
4 Correct 22 ms 12408 KB Output is correct
5 Correct 21 ms 12408 KB Output is correct
6 Correct 22 ms 12408 KB Output is correct
7 Correct 20 ms 12408 KB Output is correct
8 Correct 297 ms 18256 KB Output is correct
9 Correct 295 ms 18296 KB Output is correct
10 Correct 319 ms 18680 KB Output is correct
11 Correct 328 ms 19320 KB Output is correct
12 Correct 290 ms 17784 KB Output is correct
13 Correct 259 ms 18424 KB Output is correct
14 Correct 257 ms 18552 KB Output is correct
15 Correct 256 ms 18424 KB Output is correct
16 Correct 240 ms 18168 KB Output is correct
17 Correct 256 ms 18424 KB Output is correct
18 Correct 254 ms 18552 KB Output is correct
19 Correct 263 ms 18424 KB Output is correct
20 Correct 251 ms 18464 KB Output is correct
21 Correct 261 ms 18424 KB Output is correct
22 Correct 258 ms 18552 KB Output is correct
23 Correct 242 ms 18296 KB Output is correct
24 Correct 246 ms 18276 KB Output is correct
25 Correct 242 ms 18168 KB Output is correct
26 Correct 241 ms 18168 KB Output is correct
27 Correct 1068 ms 32664 KB Output is correct
28 Correct 998 ms 32352 KB Output is correct
29 Correct 1000 ms 31936 KB Output is correct
30 Correct 1016 ms 32632 KB Output is correct
31 Correct 993 ms 32372 KB Output is correct
32 Correct 900 ms 30872 KB Output is correct
33 Correct 900 ms 30712 KB Output is correct
34 Correct 878 ms 30688 KB Output is correct
35 Correct 914 ms 30584 KB Output is correct
36 Correct 901 ms 30776 KB Output is correct
37 Correct 910 ms 30596 KB Output is correct
38 Execution timed out 3088 ms 48228 KB Time limit exceeded
39 Halted 0 ms 0 KB -