Submission #537119

#	Time	Username	Problem	Language	Result	Execution time	Memory
537119		8e7	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	190 ms	34460 KiB

long_mansion

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> pos[maxn], del[maxn];
int rig[maxn], lef[maxn];
int c[maxn];
bool done[maxn];

pii ans[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 1;i <= n - 1;i++) cin >> c[i];	
	for (int i = 1;i <= n;i++) pos[i].push_back(-1);	
	for (int i = 1;i <= n;i++) {
		lef[i] = -1;
		rig[i] = n+2;
		ans[i] = {1, n};

		int bi;
		cin >> bi;
		for (int j = 0;j < bi;j++) {
			int x;cin>> x;
			pos[x].push_back(i);
		}
	}
	for (int i = 1;i <= n;i++) pos[i].push_back(n+2);	
	for (int i = 1;i <= n-1;i++) {
		int ri = *lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i+1);
		lef[i] = max(lef[i], ri);
		int li = *prev(upper_bound(pos[c[i]].begin(), pos[c[i]].end(), i));
		rig[i+1] = min(rig[i+1], li);
	}
	lef[0] = n+2, lef[n+1] = -1;
	rig[n+1] = -1, rig[0] = n+2;
	//debug();
	pary(rig, rig + n + 1);
	multiset<int> se;
	se.insert(n+1);	
	for (int i = n;i >= 0;i--) {
		for (int j:del[i]) {
			if (!done[j]) {
				se.erase(se.find(j));
			}
		}
		if (lef[i] >= i) {
			//debug("lef", i, lef[i]);
			int f = 0;
			auto it = se.begin();
			while (se.size()&& it != se.end()) {
				int mi = *it;
				if (mi >= lef[i]) break;
				//if (f) done[mi] = 1;
				for (int j = i+1;j < mi;j++) {
					if (i+1 > ans[j].ff || (i+1 == ans[j].ff && mi-1 < ans[j].ss)) {
						ans[j] = {i+1, mi-1};
					}
				}
				it = next(it);
				//if (f) se.erase(se.begin());
				//else f = 1;
			}
		}
		if (rig[i] < i) {
			se.insert(i);
			if (rig[i] >= 0) del[rig[i]].push_back(i);
		}
	}
	for (int i = 1;i <= n;i++) debug(i, ans[i].ff, ans[i].ss);
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << (y <= ans[x].ss && y >= ans[x].ff ? "YES" : "NO") << "\n";
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
long_mansion.cpp:55:2: note: in expansion of macro 'pary'
   55 |  pary(rig, rig + n + 1);
      |  ^~~~
long_mansion.cpp:66:8: warning: unused variable 'f' [-Wunused-variable]
   66 |    int f = 0;
      |        ^
long_mansion.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
long_mansion.cpp:87:29: note: in expansion of macro 'debug'
   87 |  for (int i = 1;i <= n;i++) debug(i, ans[i].ff, ans[i].ss);
      |                             ^~~~~

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