Submission #54704

#	Time	Username	Problem	Language	Result	Execution time	Memory
54704		ksun48	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1370 ms	145636 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;
}

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