Submission #682624

#TimeUsernameProblemLanguageResultExecution timeMemory
682624peijarLong Mansion (JOI17_long_mansion)C++17
100 / 100
352 ms41948 KiB
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif const int MAXN = 2e6; int iDeb[MAXN], iFin[MAXN], seg[MAXN]; vector<int> lst; void build(int node, int l, int r) { iDeb[node] = l, iFin[node] = r; if (l == r) { seg[node] = lst[l]; return; } build(2 * node, l, (l + r) / 2); build(2 * node + 1, (l + r) / 2 + 1, r); seg[node] = min(seg[2 * node], seg[2 * node + 1]); } int trav(int node, int from, int bound) { // premier i >= from tq lst[i] < bound if (seg[node] >= bound or iFin[node] < from) return -1; if (iDeb[node] == iFin[node]) return iDeb[node]; int lft = trav(2 * node, from, bound); if (lft == -1) return trav(2 * node + 1, from, bound); return lft; } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbChambres; cin >> nbChambres; vector<int> type(nbChambres - 1); for (int &t : type) { cin >> t; --t; } vector<vector<int>> posType(nbChambres); for (int i = 0; i < nbChambres; ++i) { int cnt; cin >> cnt; while (cnt--) { int t; cin >> t; --t; posType[t].push_back(i); } } lst.resize(nbChambres); for (int i = 1; i < nbChambres; ++i) { int t = type[i - 1]; int fst = lower_bound(posType[t].begin(), posType[t].end(), i) - posType[t].begin(); --fst; if (fst < 0) lst[i] = -1; else lst[i] = posType[t][fst]; } dbg(lst); build(1, 1, nbChambres - 1); vector<int> L(nbChambres), R(nbChambres); for (int iChambre = 0; iChambre < nbChambres; ++iChambre) { L[iChambre] = R[iChambre] = iChambre; while (L[iChambre] >= 0) { if (R[iChambre] + 1 < nbChambres) { int q = trav(1, R[iChambre] + 1, L[iChambre]); dbg(L[iChambre], R[iChambre], q); if (q == -1) R[iChambre] = nbChambres - 1; else R[iChambre] = q - 1; } if (L[iChambre] == 0) break; // can we reduce L[iChambre] ? int t = type[L[iChambre] - 1]; auto fst = lower_bound(posType[t].begin(), posType[t].end(), L[iChambre]) - posType[t].begin(); if (fst == (int)posType[t].size() or posType[t][fst] > R[iChambre]) break; L[iChambre] = L[L[iChambre] - 1]; R[iChambre] = max(R[iChambre], R[L[iChambre]]); } } dbg(L); dbg(R); int Q; cin >> Q; while (Q--) { int from, to; cin >> from >> to; --from, --to; cout << (L[from] <= to and to <= R[from] ? "YES" : "NO") << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...