Submission #54696

#	Time	Username	Problem	Language	Result	Execution time	Memory
54696		ksun48	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3017 ms	67152 KiB

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, 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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75