oj.uz

Submission #578496

# Submission time Handle Problem Language Result Execution time Memory
578496 2022-06-17T04:54:28 Z alireza_kaviani Long Mansion (JOI17_long_mansion) C++17
100 / 100
 431 ms 72192 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , q , B[MAXN] , C[MAXN] , last[MAXN] , prv[MAXN] , nxt[MAXN] , L[MAXN] , R[MAXN] , seg[MAXN << 2];
vector<int> A[MAXN];

void build(int id = 1 , int l = 1 , int r = n + 2){
	if(r - l == 1){
		seg[id] = prv[l];
		return;
	}
	int mid = l + r >> 1;
	build(lc , l , mid);
	build(rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

int Find(int ql , int qr , int x , int id = 1 , int l = 1 , int r = n + 2){
	if(qr <= l || r <= ql || seg[id] >= x)	return -1;
	if(r - l == 1)	return l;
	int mid = l + r >> 1;
	int res = Find(ql , qr , x , lc , l , mid);
	if(res != -1)	return res;
	return Find(ql , qr , x , rc , mid , r);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n;
	for(int i = 1 ; i < n ; i++)	cin >> C[i];
	for(int i = 1 ; i <= n ; i++){
		cin >> B[i];
		for(int j = 0 ; j < B[i] ; j++){
			int x;
			cin >> x;
			A[i].push_back(x);
		}
	}
	for(int i = 1 ; i <= n ; i++){
		prv[i] = last[C[i - 1]];
		for(int j : A[i]){
			last[j] = i;
		}
	}
	fill(last , last + MAXN , n + 1);
	for(int i = n ; i >= 1 ; i--){
		nxt[i] = last[C[i]];
		for(int j : A[i]){
			last[j] = i;
		}
	}
	nxt[0] = n + 1;
	build();
	for(int i = 1 ; i <= n ; i++){
		L[i] = R[i] = i;
		while(1){
			int newR = Find(R[i] + 1, n + 2, L[i]) - 1;
			int newL = (nxt[L[i] - 1] <= newR ? L[L[i] - 1] : L[i]);
			if(newL == L[i] && newR == R[i])	break;
			L[i] = newL;
			R[i] = newR;
		}
	}
	cin >> q;
	while(q--){
		int x , y;
		cin >> x >> y;
		if(L[x] <= y && y <= R[x]){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}
	}

    return 0;
}
/*

*/

Compilation message

long_mansion.cpp: In function 'void build(int, int, int)':
long_mansion.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid = l + r >> 1;
      |            ~~^~~
long_mansion.cpp: In function 'int Find(int, int, int, int, int, int)':
long_mansion.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27920 KB Output is correct
2 Correct 17 ms 28052 KB Output is correct
3 Correct 23 ms 28160 KB Output is correct
4 Correct 18 ms 27920 KB Output is correct
5 Correct 17 ms 27916 KB Output is correct
6 Correct 17 ms 27920 KB Output is correct
7 Correct 17 ms 27924 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27920 KB Output is correct
2 Correct 17 ms 28052 KB Output is correct
3 Correct 23 ms 28160 KB Output is correct
4 Correct 18 ms 27920 KB Output is correct
5 Correct 17 ms 27916 KB Output is correct
6 Correct 17 ms 27920 KB Output is correct
7 Correct 17 ms 27924 KB Output is correct
8 Correct 149 ms 33784 KB Output is correct
9 Correct 131 ms 33720 KB Output is correct
10 Correct 136 ms 34144 KB Output is correct
11 Correct 125 ms 34592 KB Output is correct
12 Correct 139 ms 33288 KB Output is correct
13 Correct 108 ms 33936 KB Output is correct
14 Correct 116 ms 33984 KB Output is correct
15 Correct 136 ms 33884 KB Output is correct
16 Correct 152 ms 33740 KB Output is correct
17 Correct 130 ms 33980 KB Output is correct
18 Correct 119 ms 34000 KB Output is correct
19 Correct 162 ms 34012 KB Output is correct
20 Correct 128 ms 33892 KB Output is correct
21 Correct 171 ms 33752 KB Output is correct
22 Correct 124 ms 33872 KB Output is correct
23 Correct 162 ms 33720 KB Output is correct
24 Correct 147 ms 33728 KB Output is correct
25 Correct 129 ms 33748 KB Output is correct
26 Correct 169 ms 33760 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 43884 KB Output is correct
2 Correct 250 ms 43704 KB Output is correct
3 Correct 336 ms 43580 KB Output is correct
4 Correct 224 ms 43768 KB Output is correct
5 Correct 315 ms 43752 KB Output is correct
6 Correct 230 ms 42540 KB Output is correct
7 Correct 263 ms 42304 KB Output is correct
8 Correct 250 ms 42296 KB Output is correct
9 Correct 246 ms 42308 KB Output is correct
10 Correct 241 ms 42208 KB Output is correct
11 Correct 215 ms 42240 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27920 KB Output is correct
2 Correct 17 ms 28052 KB Output is correct
3 Correct 23 ms 28160 KB Output is correct
4 Correct 18 ms 27920 KB Output is correct
5 Correct 17 ms 27916 KB Output is correct
6 Correct 17 ms 27920 KB Output is correct
7 Correct 17 ms 27924 KB Output is correct
8 Correct 149 ms 33784 KB Output is correct
9 Correct 131 ms 33720 KB Output is correct
10 Correct 136 ms 34144 KB Output is correct
11 Correct 125 ms 34592 KB Output is correct
12 Correct 139 ms 33288 KB Output is correct
13 Correct 108 ms 33936 KB Output is correct
14 Correct 116 ms 33984 KB Output is correct
15 Correct 136 ms 33884 KB Output is correct
16 Correct 152 ms 33740 KB Output is correct
17 Correct 130 ms 33980 KB Output is correct
18 Correct 119 ms 34000 KB Output is correct
19 Correct 162 ms 34012 KB Output is correct
20 Correct 128 ms 33892 KB Output is correct
21 Correct 171 ms 33752 KB Output is correct
22 Correct 124 ms 33872 KB Output is correct
23 Correct 162 ms 33720 KB Output is correct
24 Correct 147 ms 33728 KB Output is correct
25 Correct 129 ms 33748 KB Output is correct
26 Correct 169 ms 33760 KB Output is correct
27 Correct 344 ms 43884 KB Output is correct
28 Correct 250 ms 43704 KB Output is correct
29 Correct 336 ms 43580 KB Output is correct
30 Correct 224 ms 43768 KB Output is correct
31 Correct 315 ms 43752 KB Output is correct
32 Correct 230 ms 42540 KB Output is correct
33 Correct 263 ms 42304 KB Output is correct
34 Correct 250 ms 42296 KB Output is correct
35 Correct 246 ms 42308 KB Output is correct
36 Correct 241 ms 42208 KB Output is correct
37 Correct 215 ms 42240 KB Output is correct
38 Correct 409 ms 66892 KB Output is correct
39 Correct 424 ms 72192 KB Output is correct
40 Correct 327 ms 60296 KB Output is correct
41 Correct 431 ms 70584 KB Output is correct
42 Correct 202 ms 43352 KB Output is correct
43 Correct 222 ms 43448 KB Output is correct
44 Correct 301 ms 52532 KB Output is correct
45 Correct 278 ms 52712 KB Output is correct
46 Correct 330 ms 52856 KB Output is correct
47 Correct 213 ms 43400 KB Output is correct
48 Correct 203 ms 43292 KB Output is correct
49 Correct 284 ms 52568 KB Output is correct
50 Correct 278 ms 52592 KB Output is correct
51 Correct 289 ms 52988 KB Output is correct
52 Correct 243 ms 51544 KB Output is correct
53 Correct 295 ms 60712 KB Output is correct
54 Correct 333 ms 67824 KB Output is correct
55 Correct 304 ms 60916 KB Output is correct