제출 #241698

#제출 시각아이디문제언어결과실행 시간메모리
241698osaaateiasavtnlLong Mansion (JOI17_long_mansion)C++17
25 / 100
3082 ms68888 KiB
#include<bits/stdc++.h> using namespace std; #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int N = 1 << 20; int last[N]; int l[N << 2], r[N << 2]; void upd(int v, int tl, int tr, int ql, int qr) { if (tr < ql || qr < tl) { return; } if (ql <= tl && tr <= qr) { l[v] = max(l[v], ql); r[v] = min(r[v], qr); return; } int tm = (tl + tr) >> 1; upd(v * 2 + 1, tl, tm, ql, qr); upd(v * 2 + 2, tm + 1, tr, ql, qr); } void write(int v, int tl, int tr, vector <int> &al, vector <int> &ar) { if (tl == tr) { al[tl] = l[v]; ar[tl] = r[v]; return; } int tm = (tl + tr) >> 1; l[v * 2 + 1] = max(l[v * 2 + 1], l[v]); l[v * 2 + 2] = max(l[v * 2 + 2], l[v]); r[v * 2 + 1] = min(r[v * 2 + 1], r[v]); r[v * 2 + 2] = min(r[v * 2 + 2], r[v]); write(v * 2 + 1, tl, tm, al, ar); write(v * 2 + 2, tm + 1, tr, al, ar); } void build(int v, int tl, int tr, vector <int> &a, int tree[N << 2], bool (*comp)(int , int)) { if (tl == tr) { tree[v] = a[tl]; return; } int tm = (tl + tr) >> 1; build(v * 2 + 1, tl, tm, a, tree, comp); build(v * 2 + 2, tm + 1, tr, a, tree, comp); if (comp(tree[v * 2 + 1], tree[v * 2 + 2])) tree[v] = tree[v * 2 + 1]; else tree[v] = tree[v * 2 + 2]; } int getl(int v, int tl, int tr, int l, int r, int x, int tree[N << 2], bool (*comp)(int, int)) { if (comp(x, tree[v]) || r < tl || tr < l) return -1; if (tl == tr) return tl; int tm = (tl + tr) >> 1; int t = getl(v * 2 + 1, tl, tm, l, r, x, tree, comp); if (t != -1) return t; else return getl(v * 2 + 2, tm + 1, tr, l, r, x, tree, comp); } int getr(int v, int tl, int tr, int l, int r, int x, int tree[N << 2], bool (*comp)(int, int)) { if (comp(x, tree[v]) || r < tl || tr < l) return -1; if (tl == tr) return tl; int tm = (tl + tr) >> 1; int t = getr(v * 2 + 2, tm + 1, tr, l, r, x, tree, comp); if (t != -1) return t; else return getr(v * 2 + 1, tl, tm, l, r, x, tree, comp); } bool ls(int a, int b) { return a < b; } bool bg(int a, int b) { return a > b; } int mn[N << 2], mx[N << 2]; signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int n; cin >> n; for (int i = 0; i < (N << 2); ++i) r[i] = n - 1; vector <int> c(n-1); for (int i = 0; i < n - 1; ++i) cin >> c[i]; vector <vector <int> > a(n); for (int i = 0; i < n; ++i) { int k; cin >> k; a[i].resize(k); for (int j = 0; j < k; ++j) cin >> a[i][j]; } vector <int> l(n), r(n); for (int i = 0; i < n; ++i) { l[i] = 0; r[i] = n - 1; } vector <int> linkl(n), linkr(n); for (int i = 0; i < N; ++i) last[i] = -1; for (int i = 0; i < n - 1; ++i) { for (auto e : a[i]) last[e] = i; linkl[i] = last[c[i]]+1; } for (int i = 0; i < N; ++i) last[i] = n; for (int i = n - 1; i >= 0; --i) { if (i < n - 1) { linkr[i] = last[c[i]]-1; } for (auto e : a[i]) last[e] = i; } build(0, 0, n - 1, linkl, mn, ls); for (int i = 0; i < n; ++i) { int j = getr(0, 0, n - 1, i, linkr[i], i+1, mn, ls); if (j != -1) { upd(0, 0, n - 1, i+1, j); } } for (int j = 0; j < n; ++j) { for (int i = linkl[j]-1; i <= j; ++i) { if (j <= linkr[i]) { upd(0, 0, n - 1, i+1, j); break; } } } for (int i = 0; i < n; ++i) { if (linkr[i] == n - 1) { upd(0, 0, n - 1, i+1, n - 1); } } for (int i = 0; i < n; ++i) { if (linkl[i] == 0) { upd(0, 0, n - 1, 0, i); } } write(0, 0, n - 1, l, r); int q; cin >> q; while (q--) { int i, j; cin >> i >> j; --i; --j; if (l[i] <= j && j <= r[i]) { cout << "YES" << endl; } else { cout << "NO" << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...