Submission #682625

#TimeUsernameProblemLanguageResultExecution timeMemory
682625peijarLong Mansion (JOI17_long_mansion)C++17
100 / 100
228 ms42100 KiB
#include <bits/stdc++.h> using namespace std; inline char gc() { // like getchar() static char buf[1 << 16]; static size_t bc, be; if (bc >= be) { buf[0] = 0, bc = 0; be = fread(buf, 1, sizeof(buf), stdin); } return buf[bc++]; // returns 0 on EOF } int readInt() { int a, c; while ((a = gc()) < 40) ; if (a == '-') return -readInt(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; } 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 = readInt(); vector<int> type(nbChambres - 1); for (int &t : type) t = readInt() - 1; vector<vector<int>> posType(nbChambres); for (int i = 0; i < nbChambres; ++i) { int cnt = readInt(); while (cnt--) { int t = readInt() - 1; 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]; } 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]); 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]]); } } int Q = readInt(); while (Q--) { int from = readInt() - 1, to = readInt() - 1; 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...