oj.uz

Submission #199476

# Submission time Handle Problem Language Result Execution time Memory
199476 2020-02-01T14:03:43 Z arnold518 Long Mansion (JOI17_long_mansion) C++14
25 / 100
 1139 ms 144224 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], val[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));
	}
	void query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) { val[node]=tree[node]; return; }
		if(r<tl || tr<l) { val[node]=INF; return; }
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r);
		query2(node*2+1, mid+1, tr, l, r);
		val[node]=min(val[node*2], val[node*2+1]);
	}
	int query3(int node, int tl, int tr, int l, int r, int k)
	{
		if(l<=tl && tr<=r) { val[node*2]=tree[node*2]; val[node*2+1]=tree[node*2+1]; }
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(val[node*2+1]<=k) return query3(node*2+1, mid+1, tr, l, r, k);
		else return query3(node*2, tl, mid, l, r, k);
	}
};

struct MAXSEG
{
	int tree[MAXN*4+10], val[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));
	}
	void query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) { val[node]=tree[node]; return; }
		if(r<tl || tr<l) { val[node]=-INF; return; }
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r);
		query2(node*2+1, mid+1, tr, l, r);
		val[node]=max(val[node*2], val[node*2+1]);
	}
	int query3(int node, int tl, int tr, int l, int r, int k)
	{
		if(l<=tl && tr<=r) { val[node*2]=tree[node*2]; val[node*2+1]=tree[node*2+1]; }
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(val[node*2]>=k) return query3(node*2, tl, mid, l, r, k);
		else return query3(node*2+1, mid+1, tr, l, r, k);
	}
};

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 ", A[i]); printf("\n");
	//for(i=1; i<=N; i++) printf("%d ", B[i]); printf("\n");

	SB.init(1, 1, N, B);
	for(i=1; i<=N; i++)
	{
		SB.query2(1, 1, N, A[i], N);
		L[i]=SB.query3(1, 1, N, A[i], N, i);
		//printf("%d %d %d : %d\n", A[i], N, i, L[i]);
	}

	SA.init(1, 1, N, A);
	for(i=1; i<=N; i++)
	{
		SA.query2(1, 1, N, 1, B[i]);
		R[i]=SA.query3(1, 1, N, 1, B[i], i);
	}

	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 MINSEG::query2(int, int, int, int, int)':
long_mansion.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MINSEG::query3(int, int, int, int, int, int)':
long_mansion.cpp:46: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:59: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:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'void MAXSEG::query2(int, int, int, int, int)':
long_mansion.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In member function 'int MAXSEG::query3(int, int, int, int, int, int)':
long_mansion.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:95:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
long_mansion.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:98: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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:145: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 17 ms 12408 KB Output is correct
2 Correct 19 ms 12536 KB Output is correct
3 Correct 25 ms 12920 KB Output is correct
4 Correct 17 ms 12408 KB Output is correct
5 Correct 20 ms 12408 KB Output is correct
6 Correct 18 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 17 ms 12408 KB Output is correct
2 Correct 19 ms 12536 KB Output is correct
3 Correct 25 ms 12920 KB Output is correct
4 Correct 17 ms 12408 KB Output is correct
5 Correct 20 ms 12408 KB Output is correct
6 Correct 18 ms 12408 KB Output is correct
7 Correct 20 ms 12408 KB Output is correct
8 Correct 311 ms 14004 KB Output is correct
9 Correct 351 ms 13988 KB Output is correct
10 Correct 322 ms 14220 KB Output is correct
11 Correct 347 ms 14840 KB Output is correct
12 Correct 276 ms 14076 KB Output is correct
13 Correct 255 ms 14200 KB Output is correct
14 Correct 277 ms 14132 KB Output is correct
15 Correct 248 ms 14328 KB Output is correct
16 Correct 231 ms 14456 KB Output is correct
17 Correct 273 ms 14224 KB Output is correct
18 Correct 255 ms 14200 KB Output is correct
19 Correct 253 ms 14200 KB Output is correct
20 Correct 251 ms 14328 KB Output is correct
21 Correct 237 ms 14456 KB Output is correct
22 Correct 252 ms 14200 KB Output is correct
23 Correct 242 ms 13944 KB Output is correct
24 Correct 251 ms 14200 KB Output is correct
25 Correct 246 ms 14032 KB Output is correct
26 Correct 245 ms 14072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 29424 KB Output is correct
2 Correct 585 ms 29176 KB Output is correct
3 Correct 583 ms 29044 KB Output is correct
4 Correct 597 ms 29560 KB Output is correct
5 Correct 599 ms 29308 KB Output is correct
6 Correct 456 ms 28408 KB Output is correct
7 Correct 446 ms 28784 KB Output is correct
8 Correct 427 ms 28664 KB Output is correct
9 Correct 457 ms 28536 KB Output is correct
10 Correct 440 ms 28776 KB Output is correct
11 Correct 455 ms 28664 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12408 KB Output is correct
2 Correct 19 ms 12536 KB Output is correct
3 Correct 25 ms 12920 KB Output is correct
4 Correct 17 ms 12408 KB Output is correct
5 Correct 20 ms 12408 KB Output is correct
6 Correct 18 ms 12408 KB Output is correct
7 Correct 20 ms 12408 KB Output is correct
8 Correct 311 ms 14004 KB Output is correct
9 Correct 351 ms 13988 KB Output is correct
10 Correct 322 ms 14220 KB Output is correct
11 Correct 347 ms 14840 KB Output is correct
12 Correct 276 ms 14076 KB Output is correct
13 Correct 255 ms 14200 KB Output is correct
14 Correct 277 ms 14132 KB Output is correct
15 Correct 248 ms 14328 KB Output is correct
16 Correct 231 ms 14456 KB Output is correct
17 Correct 273 ms 14224 KB Output is correct
18 Correct 255 ms 14200 KB Output is correct
19 Correct 253 ms 14200 KB Output is correct
20 Correct 251 ms 14328 KB Output is correct
21 Correct 237 ms 14456 KB Output is correct
22 Correct 252 ms 14200 KB Output is correct
23 Correct 242 ms 13944 KB Output is correct
24 Correct 251 ms 14200 KB Output is correct
25 Correct 246 ms 14032 KB Output is correct
26 Correct 245 ms 14072 KB Output is correct
27 Correct 604 ms 29424 KB Output is correct
28 Correct 585 ms 29176 KB Output is correct
29 Correct 583 ms 29044 KB Output is correct
30 Correct 597 ms 29560 KB Output is correct
31 Correct 599 ms 29308 KB Output is correct
32 Correct 456 ms 28408 KB Output is correct
33 Correct 446 ms 28784 KB Output is correct
34 Correct 427 ms 28664 KB Output is correct
35 Correct 457 ms 28536 KB Output is correct
36 Correct 440 ms 28776 KB Output is correct
37 Correct 455 ms 28664 KB Output is correct
38 Runtime error 1139 ms 144224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Halted 0 ms 0 KB -