답안 #54698 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54698	2018-07-04T16:12:30 Z	ksun48	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3000 ms	125084 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;
}

int qmin(seg* tree, int a, int b){ // 0 is min, 1 is max
	assert(tree != NULL);
	if(b < tree->a || tree->b < a) return 1000000001;
	if(a <= tree->a && tree->b <= b) return tree->minv;
	return min(qmin(tree->l, a, b), qmin(tree->r, a, b));
}
int qmax(seg* tree, int a, int b){ // 0 is min, 1 is max
	assert(tree != NULL);
	if(b < tree->a || tree->b < a) return -1;
	if(a <= tree->a && tree->b <= b) return tree->maxv;
	return max(qmax(tree->l, a, b), qmax(tree->r, a, b));
}

//  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++){
		// find k <= nextkey[j]-1 with prevkey[k] <= j
		int s = 0;
		int e = nextkey[j];
		while(s + 1 < e){
			int m = (s+e)/2;
			if(qmin(p1, m, e-1) <= j){
				s = m;
			} else {
				e = m;
			}
		}
		conflict[j] = s;
	}

	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);
		int s = 0;
		int e = j;
		while(s + 1 < e){
			int m = (s+e)/2;
			if(qmax(p2, m, e-1) >= j){
				s = m;
			} else {
				e = m;
			}
		}
		ans[j] = j-1-s;
	}
	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	31 ms	1528 KB	Output is correct
2	Correct	28 ms	2148 KB	Output is correct
3	Correct	74 ms	3480 KB	Output is correct
4	Correct	23 ms	3480 KB	Output is correct
5	Correct	17 ms	3480 KB	Output is correct
6	Correct	19 ms	3480 KB	Output is correct
7	Correct	20 ms	3480 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	1528 KB	Output is correct
2	Correct	28 ms	2148 KB	Output is correct
3	Correct	74 ms	3480 KB	Output is correct
4	Correct	23 ms	3480 KB	Output is correct
5	Correct	17 ms	3480 KB	Output is correct
6	Correct	19 ms	3480 KB	Output is correct
7	Correct	20 ms	3480 KB	Output is correct
8	Correct	157 ms	7164 KB	Output is correct
9	Correct	144 ms	7264 KB	Output is correct
10	Correct	168 ms	8004 KB	Output is correct
11	Correct	184 ms	9232 KB	Output is correct
12	Correct	123 ms	9232 KB	Output is correct
13	Correct	142 ms	9232 KB	Output is correct
14	Correct	133 ms	9232 KB	Output is correct
15	Correct	149 ms	9232 KB	Output is correct
16	Correct	134 ms	9232 KB	Output is correct
17	Correct	135 ms	9232 KB	Output is correct
18	Correct	133 ms	9232 KB	Output is correct
19	Correct	132 ms	9232 KB	Output is correct
20	Correct	142 ms	9232 KB	Output is correct
21	Correct	140 ms	9232 KB	Output is correct
22	Correct	149 ms	9232 KB	Output is correct
23	Correct	158 ms	9232 KB	Output is correct
24	Correct	148 ms	9232 KB	Output is correct
25	Correct	191 ms	9232 KB	Output is correct
26	Correct	138 ms	9232 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2001 ms	67140 KB	Output is correct
2	Correct	1808 ms	67140 KB	Output is correct
3	Correct	1746 ms	67140 KB	Output is correct
4	Correct	1992 ms	67140 KB	Output is correct
5	Correct	1964 ms	67140 KB	Output is correct
6	Correct	1792 ms	67140 KB	Output is correct
7	Correct	1605 ms	67140 KB	Output is correct
8	Correct	1684 ms	67140 KB	Output is correct
9	Correct	1592 ms	67140 KB	Output is correct
10	Correct	1718 ms	67140 KB	Output is correct
11	Correct	1601 ms	67140 KB	Output is correct

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	1528 KB	Output is correct
2	Correct	28 ms	2148 KB	Output is correct
3	Correct	74 ms	3480 KB	Output is correct
4	Correct	23 ms	3480 KB	Output is correct
5	Correct	17 ms	3480 KB	Output is correct
6	Correct	19 ms	3480 KB	Output is correct
7	Correct	20 ms	3480 KB	Output is correct
8	Correct	157 ms	7164 KB	Output is correct
9	Correct	144 ms	7264 KB	Output is correct
10	Correct	168 ms	8004 KB	Output is correct
11	Correct	184 ms	9232 KB	Output is correct
12	Correct	123 ms	9232 KB	Output is correct
13	Correct	142 ms	9232 KB	Output is correct
14	Correct	133 ms	9232 KB	Output is correct
15	Correct	149 ms	9232 KB	Output is correct
16	Correct	134 ms	9232 KB	Output is correct
17	Correct	135 ms	9232 KB	Output is correct
18	Correct	133 ms	9232 KB	Output is correct
19	Correct	132 ms	9232 KB	Output is correct
20	Correct	142 ms	9232 KB	Output is correct
21	Correct	140 ms	9232 KB	Output is correct
22	Correct	149 ms	9232 KB	Output is correct
23	Correct	158 ms	9232 KB	Output is correct
24	Correct	148 ms	9232 KB	Output is correct
25	Correct	191 ms	9232 KB	Output is correct
26	Correct	138 ms	9232 KB	Output is correct
27	Correct	2001 ms	67140 KB	Output is correct
28	Correct	1808 ms	67140 KB	Output is correct
29	Correct	1746 ms	67140 KB	Output is correct
30	Correct	1992 ms	67140 KB	Output is correct
31	Correct	1964 ms	67140 KB	Output is correct
32	Correct	1792 ms	67140 KB	Output is correct
33	Correct	1605 ms	67140 KB	Output is correct
34	Correct	1684 ms	67140 KB	Output is correct
35	Correct	1592 ms	67140 KB	Output is correct
36	Correct	1718 ms	67140 KB	Output is correct
37	Correct	1601 ms	67140 KB	Output is correct
38	Execution timed out	3085 ms	125084 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

답안 #54698

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 75.0