oj.uz

Submission #54696

# Submission time Handle Problem Language Result Execution time Memory
54696 2018-07-04T16:08:03 Z ksun48 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 67152 KB 
#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, nextkey[j]-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, j-1) >= j){
				s = m;
			} else {
				e = m;
			}
		}
		ans[j] = j-1-s;
		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';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1528 KB Output is correct
2 Correct 30 ms 2280 KB Output is correct
3 Correct 56 ms 3388 KB Output is correct
4 Correct 20 ms 3388 KB Output is correct
5 Correct 21 ms 3388 KB Output is correct
6 Correct 20 ms 3388 KB Output is correct
7 Correct 19 ms 3388 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1528 KB Output is correct
2 Correct 30 ms 2280 KB Output is correct
3 Correct 56 ms 3388 KB Output is correct
4 Correct 20 ms 3388 KB Output is correct
5 Correct 21 ms 3388 KB Output is correct
6 Correct 20 ms 3388 KB Output is correct
7 Correct 19 ms 3388 KB Output is correct
8 Correct 141 ms 7156 KB Output is correct
9 Correct 147 ms 7156 KB Output is correct
10 Correct 158 ms 7976 KB Output is correct
11 Correct 179 ms 9144 KB Output is correct
12 Correct 121 ms 9144 KB Output is correct
13 Correct 133 ms 9144 KB Output is correct
14 Correct 134 ms 9144 KB Output is correct
15 Correct 137 ms 9144 KB Output is correct
16 Correct 136 ms 9144 KB Output is correct
17 Correct 134 ms 9144 KB Output is correct
18 Correct 150 ms 9144 KB Output is correct
19 Correct 157 ms 9144 KB Output is correct
20 Correct 136 ms 9144 KB Output is correct
21 Correct 152 ms 9144 KB Output is correct
22 Correct 146 ms 9144 KB Output is correct
23 Correct 147 ms 9144 KB Output is correct
24 Correct 139 ms 9144 KB Output is correct
25 Correct 144 ms 9144 KB Output is correct
26 Correct 146 ms 9144 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2331 ms 67152 KB Output is correct
2 Execution timed out 3017 ms 67152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1528 KB Output is correct
2 Correct 30 ms 2280 KB Output is correct
3 Correct 56 ms 3388 KB Output is correct
4 Correct 20 ms 3388 KB Output is correct
5 Correct 21 ms 3388 KB Output is correct
6 Correct 20 ms 3388 KB Output is correct
7 Correct 19 ms 3388 KB Output is correct
8 Correct 141 ms 7156 KB Output is correct
9 Correct 147 ms 7156 KB Output is correct
10 Correct 158 ms 7976 KB Output is correct
11 Correct 179 ms 9144 KB Output is correct
12 Correct 121 ms 9144 KB Output is correct
13 Correct 133 ms 9144 KB Output is correct
14 Correct 134 ms 9144 KB Output is correct
15 Correct 137 ms 9144 KB Output is correct
16 Correct 136 ms 9144 KB Output is correct
17 Correct 134 ms 9144 KB Output is correct
18 Correct 150 ms 9144 KB Output is correct
19 Correct 157 ms 9144 KB Output is correct
20 Correct 136 ms 9144 KB Output is correct
21 Correct 152 ms 9144 KB Output is correct
22 Correct 146 ms 9144 KB Output is correct
23 Correct 147 ms 9144 KB Output is correct
24 Correct 139 ms 9144 KB Output is correct
25 Correct 144 ms 9144 KB Output is correct
26 Correct 146 ms 9144 KB Output is correct
27 Correct 2331 ms 67152 KB Output is correct
28 Execution timed out 3017 ms 67152 KB Time limit exceeded
29 Halted 0 ms 0 KB -