Submission #984341

#TimeUsernameProblemLanguageResultExecution timeMemory
984341AmirAli_H1Long Mansion (JOI17_long_mansion)C++17
100 / 100
698 ms168812 KiB
// In the name of Allah #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define X real() #define Y imag() #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); int n, q; const int maxn = 5e5 + 7; const int maxlg = 20; int rmnq[maxn][maxlg], rmxq[maxn][maxlg]; int A[maxn]; vector<int> ls[maxn]; int A1[maxn], A2[maxn], ind[maxn]; vector<int> lsx[maxn]; set<int> st; int val1[maxn], val2[maxn]; int get_min(int l, int r) { int j = __lg(r - l); return min(rmnq[l][j], rmnq[r - (1 << j)][j]); } int get_max(int l, int r) { int j = __lg(r - l); return max(rmxq[l][j], rmxq[r - (1 << j)][j]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n - 1; i++) { cin >> A[i]; A[i]--; } for (int i = 1; i <= n; i++) { int T; cin >> T; while (T--) { int x; cin >> x; x--; ls[i].pb(x); } } fill(ind, ind + n, 0); for (int i = 1; i <= n; i++) { for (int j : ls[i]) ind[j] = i; if (i <= n - 1) A1[i] = ind[A[i]]; } fill(ind, ind + n, n + 1); for (int i = n; i >= 1; i--) { for (int j : ls[i]) ind[j] = i; if (i - 1 >= 1) A2[i - 1] = ind[A[i - 1]]; } st.clear(); for (int i = 0; i <= n + 1; i++) lsx[i].clear(); for (int i = 1; i <= n - 1; i++) lsx[A2[i]].pb(i); for (int i = n + 1; i >= 0; i--) { for (int j : lsx[i]) st.insert(j); if (i - 1 >= 1 && i - 1 <= n - 1) { if (A1[i - 1] == 0) val1[i - 1] = 0; else { auto it = st.lower_bound(A1[i - 1]); if (it == st.end()) val1[i - 1] = n + 1; else val1[i - 1] = (*it) + 1; } } } st.clear(); for (int i = 0; i <= n + 1; i++) lsx[i].clear(); for (int i = 1; i <= n - 1; i++) lsx[A1[i]].pb(i); for (int i = 0; i <= n + 1; i++) { for (int j : lsx[i]) st.insert(j); if (i >= 1 && i <= n - 1) { if (A2[i] == n + 1) val2[i + 1] = n + 1; else { auto it = st.lower_bound(A2[i]); if (it == st.begin()) val2[i + 1] = 0; else { it--; val2[i + 1] = *it; } } } } for (int i = n; i >= 1; i--) { rmnq[i][0] = val1[i]; rmxq[i][0] = val2[i]; for (int j = 1; j < maxlg; j++) { rmnq[i][j] = rmnq[i][j - 1]; rmxq[i][j] = rmxq[i][j - 1]; if (i + (1 << (j - 1)) <= n) { rmnq[i][j] = min(rmnq[i][j], rmnq[i + (1 << (j - 1))][j - 1]); rmxq[i][j] = max(rmxq[i][j], rmxq[i + (1 << (j - 1))][j - 1]); } } } cin >> q; while (q--) { int u, v; cin >> u >> v; if (u < v) { if (get_min(u, v) <= u) cout << "NO" << endl; else cout << "YES" << endl; } else { if (get_max(v + 1, u + 1) >= u) cout << "NO" << endl; else cout << "YES" << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...