oj.uz

Submission #73078

# Submission time Handle Problem Language Result Execution time Memory
73078 2018-08-27T15:08:57 Z szawinis Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1403 ms 76400 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;

int n, q, C[N], lf_link[N], rg_link[N], lb[N], rb[N], tmin[N << 1], tmax[N << 1];
vector<int> ls[N];

int query_min(int l, int r) {
	int res = N;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = min(tmin[l++], res);
		if(r & 1) res = min(tmin[--r], res);
	}
	return res;
}

int query_max(int l, int r) {
	int res = -1;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = max(tmax[l++], res);
		if(r & 1) res = max(tmax[--r], res);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; i++) cin >> C[i], --C[i];
	for(int i = 0, sz; i < n; i++) {
		cin >> sz;
		vector<int> keys(sz);
		for(int j = 0; j < sz; j++) {
			cin >> keys[j];
			--keys[j];
			ls[keys[j]].push_back(i);
		}
	}
	rg_link[0] = n;
	for(int i = 1; i < n; i++) {
		auto it = lower_bound(ls[C[i-1]].begin(), ls[C[i-1]].end(), i);
		if(ls[C[i-1]].empty() || it == ls[C[i-1]].end()) rg_link[i] = n;
		else rg_link[i] = *it;
	}
	lf_link[n-1] = -1;
	for(int i = 0; i < n-1; i++) {
		auto it = upper_bound(ls[C[i]].begin(), ls[C[i]].end(), i);
		if(ls[C[i]].empty() || it == ls[C[i]].begin()) lf_link[i] = -1;
		else lf_link[i] = *prev(it);
	}

	/* for(int type = 0; type < n; type++) { */
	/* 	cout << "type " << type << endl; */
	/* 	for(int i: ls[type]) cout << i << ' '; */
	/* 	cout << endl; */
	/* } */
	/* for(int i = 0; i < n; i++) cout << rg_link[i] << ' '; */
	/* cout << endl; */
	/* for(int i = 0; i < n; i++) cout << lf_link[i] << ' '; */
	/* cout << endl; */


	for(int i = 0; i < n; i++) tmin[N+i] = lf_link[i];
	for(int i = 0; i < n; i++) tmax[N+i] = rg_link[i];
	for(int i = N-1; i >= 1; i--) tmin[i] = min(tmin[i << 1], tmin[i << 1 | 1]);
	for(int i = N-1; i >= 1; i--) tmax[i] = max(tmax[i << 1], tmax[i << 1 | 1]);

	for(int r = 0; r < n; r++) {
		int s = lf_link[r] + 1, e = r;
		if(e-s+1 <= 0) {
			lb[r] = n;
			continue;
		}
		while(s < e) {
			int mid = s+e >> 1;
			if(query_max(lf_link[r] + 1, mid) > r) e = mid;
			else s = mid+1;
		}
		if(rg_link[s] <= r) lb[r] = n;
		else lb[r] = s;
	}
	for(int l = 0; l < n; l++) {
		int s = l, e = rg_link[l] - 1;
		if(e-s+1 <= 0) {
			rb[l] = -1;
			continue;
		}
		while(s < e) {
			int mid = s+e+1 >> 1;
			if(query_min(mid, rg_link[l] - 1) < l) s = mid;
			else e = mid-1;
		}
		if(lf_link[s] >= l) rb[l] = -1;
		else rb[l] = s;
	}

	/* for(int i = 0; i < n; i++) cout << lb[i] << ' '; */
	/* cout << endl; */
	/* for(int i = 0; i < n; i++) cout << rb[i] << ' '; */
	/* cout << endl; */

	for(int i = 0; i < n; i++) tmin[N+i] = lb[i];
	for(int i = 0; i < n; i++) tmax[N+i] = rb[i];
	for(int i = N-1; i >= 1; i--) tmin[i] = min(tmin[i << 1], tmin[i << 1 | 1]);
	for(int i = N-1; i >= 1; i--) tmax[i] = max(tmax[i << 1], tmax[i << 1 | 1]);
	cin >> q;
	while(q--) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		if(x < y) {
			int res = query_min(x, y-1);
			cout << (res > x ? "YES\n" : "NO\n");
		} else {
			int res = query_max(y+1, x);
			cout << (res < x ? "YES\n" : "NO\n");
		}
	}
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = s+e >> 1;
              ~^~
long_mansion.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = s+e+1 >> 1;
              ~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16888 KB Output is correct
2 Correct 27 ms 16996 KB Output is correct
3 Correct 22 ms 17216 KB Output is correct
4 Correct 22 ms 17216 KB Output is correct
5 Correct 20 ms 17216 KB Output is correct
6 Correct 21 ms 17216 KB Output is correct
7 Correct 24 ms 17216 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16888 KB Output is correct
2 Correct 27 ms 16996 KB Output is correct
3 Correct 22 ms 17216 KB Output is correct
4 Correct 22 ms 17216 KB Output is correct
5 Correct 20 ms 17216 KB Output is correct
6 Correct 21 ms 17216 KB Output is correct
7 Correct 24 ms 17216 KB Output is correct
8 Correct 184 ms 18660 KB Output is correct
9 Correct 192 ms 18672 KB Output is correct
10 Correct 193 ms 18856 KB Output is correct
11 Correct 238 ms 18960 KB Output is correct
12 Correct 166 ms 18960 KB Output is correct
13 Correct 166 ms 18960 KB Output is correct
14 Correct 208 ms 18960 KB Output is correct
15 Correct 156 ms 18988 KB Output is correct
16 Correct 158 ms 19116 KB Output is correct
17 Correct 151 ms 19116 KB Output is correct
18 Correct 211 ms 19116 KB Output is correct
19 Correct 199 ms 19116 KB Output is correct
20 Correct 200 ms 19116 KB Output is correct
21 Correct 174 ms 19324 KB Output is correct
22 Correct 177 ms 19324 KB Output is correct
23 Correct 158 ms 19324 KB Output is correct
24 Correct 153 ms 19324 KB Output is correct
25 Correct 242 ms 19324 KB Output is correct
26 Correct 193 ms 19324 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 23896 KB Output is correct
2 Correct 420 ms 23896 KB Output is correct
3 Correct 339 ms 23896 KB Output is correct
4 Correct 329 ms 23896 KB Output is correct
5 Correct 334 ms 23896 KB Output is correct
6 Correct 308 ms 23896 KB Output is correct
7 Correct 313 ms 23896 KB Output is correct
8 Correct 284 ms 23896 KB Output is correct
9 Correct 284 ms 23896 KB Output is correct
10 Correct 341 ms 23896 KB Output is correct
11 Correct 410 ms 23896 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16888 KB Output is correct
2 Correct 27 ms 16996 KB Output is correct
3 Correct 22 ms 17216 KB Output is correct
4 Correct 22 ms 17216 KB Output is correct
5 Correct 20 ms 17216 KB Output is correct
6 Correct 21 ms 17216 KB Output is correct
7 Correct 24 ms 17216 KB Output is correct
8 Correct 184 ms 18660 KB Output is correct
9 Correct 192 ms 18672 KB Output is correct
10 Correct 193 ms 18856 KB Output is correct
11 Correct 238 ms 18960 KB Output is correct
12 Correct 166 ms 18960 KB Output is correct
13 Correct 166 ms 18960 KB Output is correct
14 Correct 208 ms 18960 KB Output is correct
15 Correct 156 ms 18988 KB Output is correct
16 Correct 158 ms 19116 KB Output is correct
17 Correct 151 ms 19116 KB Output is correct
18 Correct 211 ms 19116 KB Output is correct
19 Correct 199 ms 19116 KB Output is correct
20 Correct 200 ms 19116 KB Output is correct
21 Correct 174 ms 19324 KB Output is correct
22 Correct 177 ms 19324 KB Output is correct
23 Correct 158 ms 19324 KB Output is correct
24 Correct 153 ms 19324 KB Output is correct
25 Correct 242 ms 19324 KB Output is correct
26 Correct 193 ms 19324 KB Output is correct
27 Correct 323 ms 23896 KB Output is correct
28 Correct 420 ms 23896 KB Output is correct
29 Correct 339 ms 23896 KB Output is correct
30 Correct 329 ms 23896 KB Output is correct
31 Correct 334 ms 23896 KB Output is correct
32 Correct 308 ms 23896 KB Output is correct
33 Correct 313 ms 23896 KB Output is correct
34 Correct 284 ms 23896 KB Output is correct
35 Correct 284 ms 23896 KB Output is correct
36 Correct 341 ms 23896 KB Output is correct
37 Correct 410 ms 23896 KB Output is correct
38 Correct 1233 ms 32716 KB Output is correct
39 Correct 953 ms 35204 KB Output is correct
40 Correct 791 ms 35204 KB Output is correct
41 Correct 537 ms 35204 KB Output is correct
42 Correct 346 ms 35204 KB Output is correct
43 Correct 271 ms 35204 KB Output is correct
44 Correct 373 ms 35204 KB Output is correct
45 Correct 499 ms 35204 KB Output is correct
46 Correct 547 ms 35204 KB Output is correct
47 Correct 355 ms 35204 KB Output is correct
48 Correct 394 ms 35204 KB Output is correct
49 Correct 438 ms 35204 KB Output is correct
50 Correct 372 ms 35204 KB Output is correct
51 Correct 468 ms 35204 KB Output is correct
52 Correct 735 ms 36140 KB Output is correct
53 Correct 908 ms 52636 KB Output is correct
54 Correct 1403 ms 71388 KB Output is correct
55 Correct 1069 ms 76400 KB Output is correct