답안 #54704 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54704	2018-07-04T16:32:54 Z	ksun48	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1370 ms	145636 KB

long_mansion

#include <bits/stdc++.h>
using namespace std;

struct seg{
	seg *l, *r;
	int a, b;
	int minv, maxv;
};

seg* make(vector<int>&x, int a, int b){
	seg* z = new seg();
	z->a = a;
	z->b = b;
	if(a == b){
		z->l = z->r = NULL;
		z->minv = z->maxv = x[a];
	} else {
		z->l = make(x, a, (a+b)/2);
		z->r = make(x, (a+b)/2+1, b);
		z->minv = min(z->l->minv, z->r->minv);
		z->maxv = max(z->l->maxv, z->r->maxv);
	}
	return z;
}

void kill(seg* r){
	if(r == NULL) return;
	kill(r->l);
	kill(r->r);
	delete r;
}

int idxatleast(seg* tree, int a, int b, int v){
	if(tree->maxv < v || b < tree->a || tree->b < a) return -1;
	if(tree->a == tree->b) return tree->a;
	int idxr = idxatleast(tree->r, a, b, v);
	if(idxr != -1) return idxr;
	int idxl = idxatleast(tree->l, a, b, v);
	if(idxl != -1) return idxl;
	return -1;
}
int idxatmost(seg* tree, int a, int b, int v){
	if(tree->minv > v || b < tree->a || tree->b < a) return -1;
	if(tree->a == tree->b) return tree->a;
	int idxr = idxatmost(tree->r, a, b, v);
	if(idxr != -1) return idxr;
	int idxl = idxatmost(tree->l, a, b, v);
	if(idxl != -1) return idxl;
	return -1;
}

//  0|   1|   2|   3|   4|   6|
//    23    1    1    3    4
vector<int> solve(int n, vector<int> &walls, vector<vector<int> > &keys){
	// keys range from 0 to n
	// rooms 0 ... n+1
	// rooms
	// 0    1    2    ...      n    n+1
	//   0|   1|   2|     n-1|   n|  
	// walls

	// for rooms 1 ... n, returns leftmost reachable room
	vector<vector<int> > keylocations(n+1);
	for(int i = 0; i <= n+1; i++){
		for(int a : keys[i]){
			keylocations[a].push_back(i);
		}
	}
	vector<int> prevkey(n+1);
	vector<int> nextkey(n+1);
	for(int i = 0; i <= n; i++){
		int type = walls[i];
		auto it = lower_bound(keylocations[type].begin(), keylocations[type].end(), i+1);
		nextkey[i] = *it;
		prevkey[i] = *(it-1);
	}

	// for each wall, find farthest one so that there's a conflict
	// then for a starting room, find dist to closest so that there is a conflict that extends past it

	seg *p1 = make(prevkey, 0, prevkey.size()-1);
	vector<int> conflict(n+1, -1);
	for(int j = 0; j <= n; j++){
		conflict[j] = idxatmost(p1, 0, nextkey[j]-1, j);
	}
	kill(p1);

	seg *p2 = make(conflict, 0, conflict.size()-1);
	vector<int> ans(n+2, -1);
	for(int j = 1; j <= n; j++){
		// ans[j] = j-1- max(k < j with c[k] >= j);
		ans[j] = j - 1 - idxatleast(p2, 0, j-1, j);
	}
	kill(p2);
	return ans;
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	vector<int> walls; // what key need
	walls.push_back(0);
	for(int i = 1; i < n; i++){
		int c;
		cin >> c;
		walls.push_back(c);
	}
	walls.push_back(0);
	vector<vector<int> > keys(n+2);
	for(int i = 0; i <= n; i++){
		keys[0].push_back(i);
		keys[n+1].push_back(i);
	}
	for(int i = 1; i <= n; i++){
		int b;
		cin >> b;
		keys[i].resize(b);
		for(int j = 0; j < b; j++){
			cin >> keys[i][j];
		}
	}
	int q;
	cin >> q;
	vector<int> x(q);
	vector<int> y(q);
	for(int i = 0; i < q; i++){
		cin >> x[i] >> y[i];
	}

	vector<int> leftans = solve(n, walls, keys);
	reverse(walls.begin(), walls.end());
	reverse(keys.begin(), keys.end());
	vector<int> rightans = solve(n, walls, keys);
	reverse(rightans.begin(), rightans.end());
	for(int i = 0; i < q; i++){
		if(y[i]-x[i] <= rightans[x[i]] && y[i]-x[i] >= -leftans[x[i]]){
			cout << "YES" << '\n';
		} else {
			cout << "NO" << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	888 KB	Output is correct
2	Correct	8 ms	1252 KB	Output is correct
3	Correct	13 ms	1836 KB	Output is correct
4	Correct	6 ms	1836 KB	Output is correct
5	Correct	6 ms	1836 KB	Output is correct
6	Correct	7 ms	1836 KB	Output is correct
7	Correct	6 ms	1836 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	888 KB	Output is correct
2	Correct	8 ms	1252 KB	Output is correct
3	Correct	13 ms	1836 KB	Output is correct
4	Correct	6 ms	1836 KB	Output is correct
5	Correct	6 ms	1836 KB	Output is correct
6	Correct	7 ms	1836 KB	Output is correct
7	Correct	6 ms	1836 KB	Output is correct
8	Correct	134 ms	6548 KB	Output is correct
9	Correct	129 ms	6548 KB	Output is correct
10	Correct	133 ms	6956 KB	Output is correct
11	Correct	132 ms	7524 KB	Output is correct
12	Correct	150 ms	7524 KB	Output is correct
13	Correct	121 ms	7524 KB	Output is correct
14	Correct	121 ms	7524 KB	Output is correct
15	Correct	129 ms	7524 KB	Output is correct
16	Correct	125 ms	7524 KB	Output is correct
17	Correct	121 ms	7524 KB	Output is correct
18	Correct	135 ms	7524 KB	Output is correct
19	Correct	129 ms	7524 KB	Output is correct
20	Correct	183 ms	7524 KB	Output is correct
21	Correct	127 ms	7524 KB	Output is correct
22	Correct	123 ms	7524 KB	Output is correct
23	Correct	126 ms	7524 KB	Output is correct
24	Correct	141 ms	7524 KB	Output is correct
25	Correct	138 ms	7524 KB	Output is correct
26	Correct	135 ms	7524 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	412 ms	32020 KB	Output is correct
2	Correct	396 ms	32020 KB	Output is correct
3	Correct	444 ms	32136 KB	Output is correct
4	Correct	404 ms	32136 KB	Output is correct
5	Correct	386 ms	32136 KB	Output is correct
6	Correct	363 ms	32136 KB	Output is correct
7	Correct	364 ms	32136 KB	Output is correct
8	Correct	419 ms	32136 KB	Output is correct
9	Correct	455 ms	32136 KB	Output is correct
10	Correct	436 ms	32136 KB	Output is correct
11	Correct	376 ms	32136 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	888 KB	Output is correct
2	Correct	8 ms	1252 KB	Output is correct
3	Correct	13 ms	1836 KB	Output is correct
4	Correct	6 ms	1836 KB	Output is correct
5	Correct	6 ms	1836 KB	Output is correct
6	Correct	7 ms	1836 KB	Output is correct
7	Correct	6 ms	1836 KB	Output is correct
8	Correct	134 ms	6548 KB	Output is correct
9	Correct	129 ms	6548 KB	Output is correct
10	Correct	133 ms	6956 KB	Output is correct
11	Correct	132 ms	7524 KB	Output is correct
12	Correct	150 ms	7524 KB	Output is correct
13	Correct	121 ms	7524 KB	Output is correct
14	Correct	121 ms	7524 KB	Output is correct
15	Correct	129 ms	7524 KB	Output is correct
16	Correct	125 ms	7524 KB	Output is correct
17	Correct	121 ms	7524 KB	Output is correct
18	Correct	135 ms	7524 KB	Output is correct
19	Correct	129 ms	7524 KB	Output is correct
20	Correct	183 ms	7524 KB	Output is correct
21	Correct	127 ms	7524 KB	Output is correct
22	Correct	123 ms	7524 KB	Output is correct
23	Correct	126 ms	7524 KB	Output is correct
24	Correct	141 ms	7524 KB	Output is correct
25	Correct	138 ms	7524 KB	Output is correct
26	Correct	135 ms	7524 KB	Output is correct
27	Correct	412 ms	32020 KB	Output is correct
28	Correct	396 ms	32020 KB	Output is correct
29	Correct	444 ms	32136 KB	Output is correct
30	Correct	404 ms	32136 KB	Output is correct
31	Correct	386 ms	32136 KB	Output is correct
32	Correct	363 ms	32136 KB	Output is correct
33	Correct	364 ms	32136 KB	Output is correct
34	Correct	419 ms	32136 KB	Output is correct
35	Correct	455 ms	32136 KB	Output is correct
36	Correct	436 ms	32136 KB	Output is correct
37	Correct	376 ms	32136 KB	Output is correct
38	Correct	1264 ms	103056 KB	Output is correct
39	Correct	1370 ms	137920 KB	Output is correct
40	Correct	1042 ms	137920 KB	Output is correct
41	Correct	1356 ms	145636 KB	Output is correct
42	Correct	449 ms	145636 KB	Output is correct
43	Correct	415 ms	145636 KB	Output is correct
44	Correct	801 ms	145636 KB	Output is correct
45	Correct	853 ms	145636 KB	Output is correct
46	Correct	1038 ms	145636 KB	Output is correct
47	Correct	434 ms	145636 KB	Output is correct
48	Correct	433 ms	145636 KB	Output is correct
49	Correct	833 ms	145636 KB	Output is correct
50	Correct	1025 ms	145636 KB	Output is correct
51	Correct	929 ms	145636 KB	Output is correct
52	Correct	739 ms	145636 KB	Output is correct
53	Correct	978 ms	145636 KB	Output is correct
54	Correct	1178 ms	145636 KB	Output is correct
55	Correct	914 ms	145636 KB	Output is correct

답안 #54704

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
75.0 / 75.0