Submission #851336

#	Time	Username	Problem	Language	Result	Execution time	Memory
851336		mickey080929	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1077 ms	88912 KiB

long_mansion

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;

const int inf = 1e9;

struct SegmentTree{
public:
	int n, tree_iden;
	vector<int> tree;
	function<int(int,int)> Merge;
	SegmentTree(int _tree_iden, function<int(int,int)> _Merge) :
		tree_iden(_tree_iden), Merge(_Merge) {}
	void init(int _n) {
		n = _n;
		int sz = 1<<(Log2(n)+1);
		tree.assign(sz, tree_iden);
	}
	void update_point(int tar, int val) { update_point(1, 1, n, tar, val); }
	int query_range(int l, int r) { return query_range(1, 1, n, l, r); }
	int find_left(int l, int r) { return find_left(1, 1, n, l, r); }
	int find_right(int l, int r) { return find_right(1, 1, n, l, r); }
private:
	static int Log2(int n) {
		int ret = 0;
		while (n > 1 << ret) ret ++;
		return ret;
	}
	void Pull(int node) { tree[node] = Merge(tree[node<<1], tree[node<<1|1]); }
	void update_point(int node, int s, int e, int tar, int val) {
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = val;
			return;
		}
		int mid = s + e >> 1;
		update_point(node<<1, s, mid, tar, val);
		update_point(node<<1|1, mid+1, e, tar, val);
		Pull(node);
	}
	int query_range(int node, int s, int e, int l, int r) {
		if (l > e || s > r) return tree_iden;
		if (l <= s && e <= r) return tree[node];
		int mid = s + e >> 1;
		return Merge(query_range(node<<1, s, mid, l, r), query_range(node<<1|1, mid+1, e, l, r));
	}
	int find_left(int node, int s, int e, int l, int r) {
		if (l > e || s > r || tree[node] == tree_iden) return -1; 
        if (s == e) return s;
        int mid = s + e >> 1;
        int res = find_left(node<<1, s, mid, l, r);
        if (res == -1) res = find_left(node<<1|1, mid+1, e, l, r);
        return res;
    }
    int find_right(int node, int s, int e, int l, int r) {
		if (l > e || s > r || tree[node] == tree_iden) return -1; 
        if (s == e) return s;
        int mid = s + e >> 1;
        int res = find_right(node<<1|1, mid+1, e, l, r);
        if (res == -1) res = find_right(node<<1, s, mid, l, r);
        return res;
    }
};

struct LazySegmentTree{
public:
	int n, tree_iden, lazy_iden;
	vector<int> tree;
	vector<int> lazy;
	function<int(int,int)> Merge;
	LazySegmentTree(int _tree_iden, int _lazy_iden, function<int(int,int)> _Merge) : 
		tree_iden(_tree_iden), lazy_iden(_lazy_iden), Merge(_Merge) {}
	void init(int _n) {
		n = _n;
		int sz = 1<<(Log2(n)+1);
		tree.assign(sz, tree_iden);
		lazy.assign(sz, lazy_iden);
	}
	void update_point(int tar, int val) { update_point(1, 1, n, tar, val); }
	void update_range(int l, int r, int val) { update_range(1, 1, n, l, r, val); }
	int query_range(int l, int r) { return query_range(1, 1, n, l, r); }
private:
	static int Log2(int n) {
		int ret = 0;
		while (n > 1 << ret) ret ++;
		return ret;
	}
	void Pull(int node) { tree[node] = Merge(tree[node<<1], tree[node<<1|1]); }
	void Push(int node, int s, int e) {
		if (lazy[node] == lazy_iden) return;
		tree[node] = lazy[node];
		if (s != e) {
			lazy[node<<1] = lazy[node];
			lazy[node<<1|1] = lazy[node];
		}
		lazy[node] = lazy_iden;
	}
	void update_point(int node, int s, int e, int tar, int val) {
		Push(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = val;
			return;
		}
		int mid = s + e >> 1;
		update_point(node<<1, s, mid, tar, val);
		update_point(node<<1|1, mid+1, e, tar, val);
		Pull(node);
	}
	void update_range(int node, int s, int e, int l, int r, int val) {
		Push(node, s, e);
		if (l > e || s > r) return;
		if (l <= s && e <= r) {
			lazy[node] = val;
			Push(node, s, e);
			return;
		}
		int mid = s + e >> 1;
		update_range(node<<1, s, mid, l, r, val);
		update_range(node<<1|1, mid+1, e, l, r, val);
		Pull(node);
	}
	int query_range(int node, int s, int e, int l, int r) {
		Push(node, s, e);
		if (l > e || s > r) return tree_iden;
		if (l <= s && e <= r) return tree[node];
		int mid = s + e >> 1;
		return Merge(query_range(node<<1, s, mid, l, r), query_range(node<<1|1, mid+1, e, l, r));
	}
};

SegmentTree seg(0, [] (int l, int r) { return l + r; });
LazySegmentTree Rseg(inf, inf, [] (int l, int r) { return min(l, r); });
LazySegmentTree Lseg(-inf, -inf, [] (int l, int r) { return max(l, r); });
 
int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); 
	int n, q;
	cin >> n ;
	vector<int> C(n);
	for (int i=1; i<=n-1; i++) cin >> C[i];
	vector<vector<int>> keys(n+1, vector<int>());
	for (int i=1; i<=n; i++) {
		int k; cin >> k;
		keys[i].resize(k);
		for (int j=0; j<k; j++) {
			cin >> keys[i][j];
		}
	}
	vector<int> L(n), R(n);
	vector<int> last(n+1, 0);
	for (int i=1; i<=n-1; i++) {
		for (auto &j : keys[i]) last[j] = i;
		L[i] = last[C[i]];
	}
	fill(last.begin(), last.end(), n+1);
	for (int i=n-1; i>=1; i--) {
		for (auto &j : keys[i+1]) last[j] = i+1;
		R[i] = last[C[i]];
	}
	seg.init(n);
	Rseg.init(n);
	Lseg.init(n);
	vector<vector<int>> mark(n+2, vector<int>());
	for (int i=1; i<=n-1; i++) mark[L[i]].push_back(i);
	for (auto &i : mark[0]) seg.update_point(i, 1);
	for (int i=1; i<=n-1; i++) {
		for (auto &j : mark[i]) seg.update_point(j, 1);
		if (R[i] == n+1) Lseg.update_range(i+1, n, i+1);
		else {
			int ret = seg.find_right(i+1, R[i]-1);
			if (ret != -1) Lseg.update_range(i+1, ret, i+1);
		}
	}
	seg.init(n);
	for (int i=0; i<=n+1; i++) mark[i].clear();
	for (int i=1; i<=n-1; i++) mark[R[i]].push_back(i);
	for (auto &i : mark[n+1]) seg.update_point(i, 1);
	for (int i=n-1; i>=1; i--) {
		for (auto &j : mark[i+1]) seg.update_point(j, 1);
		if (L[i] == 0) Rseg.update_range(1, i, i);
		else { 
			int ret = seg.find_left(L[i], i);
			if (ret != -1) Rseg.update_range(ret+1, i, i);
		}
	}
	cin >> q;
	while (q --) {
		int s, e;
		cin >> s >> e;
		if (Lseg.query_range(s,s) <= e && e <= Rseg.query_range(s,s)) cout << "YES\n";
		else cout << "NO\n";
	}

}

Compilation message (stderr)

long_mansion.cpp: In member function 'void SegmentTree::update_point(int, int, int, int, int)':
long_mansion.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid = s + e >> 1;
      |             ~~^~~
long_mansion.cpp: In member function 'int SegmentTree::query_range(int, int, int, int, int)':
long_mansion.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = s + e >> 1;
      |             ~~^~~
long_mansion.cpp: In member function 'int SegmentTree::find_left(int, int, int, int, int)':
long_mansion.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = s + e >> 1;
      |                   ~~^~~
long_mansion.cpp: In member function 'int SegmentTree::find_right(int, int, int, int, int)':
long_mansion.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = s + e >> 1;
      |                   ~~^~~
long_mansion.cpp: In member function 'void LazySegmentTree::update_point(int, int, int, int, int)':
long_mansion.cpp:109:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |   int mid = s + e >> 1;
      |             ~~^~~
long_mansion.cpp: In member function 'void LazySegmentTree::update_range(int, int, int, int, int, int)':
long_mansion.cpp:122:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |   int mid = s + e >> 1;
      |             ~~^~~
long_mansion.cpp: In member function 'int LazySegmentTree::query_range(int, int, int, int, int)':
long_mansion.cpp:131:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |   int mid = s + e >> 1;
      |             ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75