제출 #1080047

#제출 시각아이디문제언어결과실행 시간메모리
1080047ThanhsLong Mansion (JOI17_long_mansion)C++14
100 / 100
391 ms73736 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long // #define double long double #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) ((x) * (x)) #define fi first #define se second #define aint(x) x.begin(), x.end() // mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); // int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);} const int NM = 5e5 + 5; int n, b[NM], c[NM], a[NM], L[NM]; struct ST1 { int dt[4 * NM]; void build(int x = 1, int l = 1, int r = n) { if (l == r) { dt[x] = b[l]; return; } int m = l + r >> 1; build(x << 1, l, m); build(x << 1 | 1, m + 1, r); dt[x] = min(dt[x << 1], dt[x << 1 | 1]); } int get(int i, int l, int x = 1, int lx = 1, int rx = n) { // cout << i << ' ' << l << ' ' << x << ' ' << lx << ' ' << rx << endl; if (rx < l || dt[x] >= i) return rx + 1; if (lx == rx) return lx; int m = lx + rx >> 1; int res = m + 1; if (dt[x << 1] < i) res = get(i, l, x << 1, lx, m); if (res != m + 1) return res; return get(i, l, x << 1 | 1, m + 1, rx); } }st1; struct ST2 { int dt[4 * NM]; void build(int x = 1, int l = 1, int r = n) { if (l == r) { dt[x] = c[l + 1]; return; } int m = l + r >> 1; build(x << 1, l, m); build(x << 1 | 1, m + 1, r); dt[x] = max(dt[x << 1], dt[x << 1 | 1]); } int get(int i, int r, int x = 1, int lx = 1, int rx = n) { if (lx > r || dt[x] <= i) return lx - 1; if (lx == rx) return lx; int m = lx + rx >> 1; int res = m; if (dt[x << 1 | 1] > i) res = get(i, r, x << 1 | 1, m + 1, rx); if (res != m) return res; return get(i, r, x << 1, lx, m); } }st2; struct ST3 { pair<int, int> dt[4 * NM]; void build(int x = 1, int l = 1, int r = n) { dt[x] = {n + 1, 0}; if (l == r) return; int m = l + r >> 1; build(x << 1, l, m); build(x << 1 | 1, m + 1, r); } void upd(pair<int, int> v, int i, int x = 1, int lx = 1, int rx = n) { if (lx == rx) { dt[x] = v; return; } int m = lx + rx >> 1; if (m >= i) upd(v, i, x << 1, lx, m); else upd(v, i, x << 1 | 1, m + 1, rx); dt[x].fi = min(dt[x << 1].fi, dt[x << 1 | 1].fi); dt[x].se = max(dt[x << 1].se, dt[x << 1 | 1].se); } pair<int, int> get(int l, int r, int x = 1, int lx = 1, int rx = n) { if (l > rx || lx > r || l > r) return {n + 1, 0}; if (lx >= l && rx <= r) return dt[x]; int m = lx + rx >> 1; pair<int, int> res1 = get(l, r, x << 1, lx, m); pair<int, int> res2 = get(l, r, x << 1 | 1, m + 1, rx); return {min(res1.fi, res2.fi), max(res1.se, res2.se)}; } }st3; int l[NM], r[NM]; vector<int> v[NM]; void solve() { cin >> n; for (int i = 2; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { b[i] = L[a[i]]; int t; cin >> t; while (t--) { int x; cin >> x; setmax(L[x], i); v[i].push_back(x); } } for (int i = 1; i <= n; i++) L[i] = n + 1; for (int i = n; i >= 1; i--) { for (auto x : v[i]) setmin(L[x], i); c[i] = L[a[i]]; } b[1] = n + 1; st1.build(); st2.build(); st3.build(); for (int i = 1; i <= n; i++) { l[i] = r[i] = i; while (1) { int ll = l[i], rr = r[i]; r[i] = st1.get(l[i], i + 1) - 1; l[i] = st2.get(r[i], i - 1) + 1; pair<int, int> res = st3.get(l[i], i - 1); setmin(l[i], res.fi); setmax(r[i], res.se); if (l[i] == ll && r[i] == rr) break; } st3.upd({l[i], r[i]}, i); } int q; cin >> q; while (q--) { int x, y; cin >> x >> y; cout << (l[x] <= y && r[x] >= y ? "YES\n" : "NO\n"); } } int main() { fastIO if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); } int tc = 1; // cin >> tc; while (tc--) solve(); }

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In member function 'void ST1::build(int, int, int)':
long_mansion.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'int ST1::get(int, int, int, int, int)':
long_mansion.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'void ST2::build(int, int, int)':
long_mansion.cpp:64:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'int ST2::get(int, int, int, int, int)':
long_mansion.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'void ST3::build(int, int, int)':
long_mansion.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'void ST3::upd(std::pair<int, int>, int, int, int, int)':
long_mansion.cpp:104:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'std::pair<int, int> ST3::get(int, int, int, int, int)':
long_mansion.cpp:118:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...