답안 #54693 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54693	2018-07-04T16:01:14 Z	ksun48	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3000 ms	60560 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>&r, 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 = r[a];
	} else {
		z->l = make(r, a, (a+b)/2);
		z->r = make(r, (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 query(seg* tree, int a, int b, int type){ // 0 is min, 1 is max
	assert(tree != NULL);
	if(b < tree->a || tree->b < a) return -1 + (1-type) * 1000000001;
	if(a <= tree->a && tree->b <= b) return tree->minv;
	if(type == 0){
		return min(query(tree->l, a, b, type), query(tree->r, a, b, type));
	} else if(type == 1){
		return min(query(tree->l, a, b, type), query(tree->r, a, b, type));
	}
}

//  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(query(p1, m, nextkey[j]-1, 0) <= j){
				s = m;
			} else {
				e = m;
			}
		}
		conflict[j] = s;
	}

	vector<int> ans(n+2, -1);
	for(int j = 1; j <= n; j++){
		// ans[j] = j-1- max(k < j with c[k] >= j);
		for(int k = j-1; k >= 0; k--){
			if(conflict[k] >= j){
				ans[j] = j-1-k;
				break;
			}
		}
	}
	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';
		}
	}
}

Compilation message

long_mansion.cpp: In function 'int query(seg*, int, int, int)':
long_mansion.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	1272 KB	Output is correct
2	Correct	20 ms	1832 KB	Output is correct
3	Correct	37 ms	2484 KB	Output is correct
4	Correct	14 ms	2484 KB	Output is correct
5	Correct	15 ms	2484 KB	Output is correct
6	Correct	14 ms	2484 KB	Output is correct
7	Correct	12 ms	2484 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	1272 KB	Output is correct
2	Correct	20 ms	1832 KB	Output is correct
3	Correct	37 ms	2484 KB	Output is correct
4	Correct	14 ms	2484 KB	Output is correct
5	Correct	15 ms	2484 KB	Output is correct
6	Correct	14 ms	2484 KB	Output is correct
7	Correct	12 ms	2484 KB	Output is correct
8	Correct	171 ms	6904 KB	Output is correct
9	Correct	140 ms	6904 KB	Output is correct
10	Correct	177 ms	7444 KB	Output is correct
11	Correct	175 ms	8416 KB	Output is correct
12	Correct	126 ms	8416 KB	Output is correct
13	Correct	172 ms	8416 KB	Output is correct
14	Correct	140 ms	8416 KB	Output is correct
15	Correct	132 ms	8416 KB	Output is correct
16	Correct	147 ms	8416 KB	Output is correct
17	Correct	157 ms	8416 KB	Output is correct
18	Correct	186 ms	8416 KB	Output is correct
19	Correct	132 ms	8416 KB	Output is correct
20	Correct	169 ms	8416 KB	Output is correct
21	Correct	132 ms	8416 KB	Output is correct
22	Correct	128 ms	8416 KB	Output is correct
23	Correct	133 ms	8416 KB	Output is correct
24	Correct	135 ms	8416 KB	Output is correct
25	Correct	137 ms	8416 KB	Output is correct
26	Correct	204 ms	8416 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1667 ms	48236 KB	Output is correct
2	Correct	2007 ms	55072 KB	Output is correct
3	Execution timed out	3031 ms	60560 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	1272 KB	Output is correct
2	Correct	20 ms	1832 KB	Output is correct
3	Correct	37 ms	2484 KB	Output is correct
4	Correct	14 ms	2484 KB	Output is correct
5	Correct	15 ms	2484 KB	Output is correct
6	Correct	14 ms	2484 KB	Output is correct
7	Correct	12 ms	2484 KB	Output is correct
8	Correct	171 ms	6904 KB	Output is correct
9	Correct	140 ms	6904 KB	Output is correct
10	Correct	177 ms	7444 KB	Output is correct
11	Correct	175 ms	8416 KB	Output is correct
12	Correct	126 ms	8416 KB	Output is correct
13	Correct	172 ms	8416 KB	Output is correct
14	Correct	140 ms	8416 KB	Output is correct
15	Correct	132 ms	8416 KB	Output is correct
16	Correct	147 ms	8416 KB	Output is correct
17	Correct	157 ms	8416 KB	Output is correct
18	Correct	186 ms	8416 KB	Output is correct
19	Correct	132 ms	8416 KB	Output is correct
20	Correct	169 ms	8416 KB	Output is correct
21	Correct	132 ms	8416 KB	Output is correct
22	Correct	128 ms	8416 KB	Output is correct
23	Correct	133 ms	8416 KB	Output is correct
24	Correct	135 ms	8416 KB	Output is correct
25	Correct	137 ms	8416 KB	Output is correct
26	Correct	204 ms	8416 KB	Output is correct
27	Correct	1667 ms	48236 KB	Output is correct
28	Correct	2007 ms	55072 KB	Output is correct
29	Execution timed out	3031 ms	60560 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

답안 #54693

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 15.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 15.0

Subtask #4
0 / 75.0