Submission #974870

#	Time	Username	Problem	Language	Result	Execution time	Memory
974870		abczz	Long Mansion (JOI17_long_mansion)	C++14	20 / 100	1020 ms	101700 KiB

long_mansion

#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long

using namespace std;

vector <ll> V[500000], X, Y;
map <ll, ll> mp;
ll n, k, a, b, q, C[500000], L[500000], R[500000], P[500000];
vector <ll> MX[500000], MN[500000];

struct SegTree{
  vector <ll> st{vector <ll>(2000000, 1e18)};
  vector <ll> st2{vector <ll>(2000000, -1e18)};
  void push(ll id) {
    st[id*2] = min(st[id], st[id*2]);
    st[id*2+1] = min(st[id], st[id*2+1]);
    st2[id*2] = max(st2[id], st2[id*2]);
    st2[id*2+1] = max(st2[id], st2[id*2+1]);
  }
  void updateMN(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[id] = min(st[id], w);
      return;
    }
    ll mid = (l+r)/2;
    updateMN(id*2, l, mid, ql, qr, w);
    updateMN(id*2+1, mid+1, r, ql, qr, w);
  }
  void updateMX(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st2[id] = max(st2[id], w);
      return;
    }
    ll mid = (l+r)/2;
    updateMX(id*2, l, mid, ql, qr, w);
    updateMX(id*2+1, mid+1, r, ql, qr, w);
  }
  array<ll, 2> query(ll id, ll l, ll r, ll q) {
    if (l == r) return {st[id], st2[id]};
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
} ST;
int main() {
  cin >> n;
  for (int i=0; i<n-1; ++i) {
    cin >> C[i];
    --C[i];
  }
  for (int i=0; i<n; ++i) {
    P[i] = -1e18;
    cin >> k;
    while (k--) {
      cin >> a;
      --a;
      V[i].push_back(a);
    }
  }
  for (int i=0; i<n-1; ++i) {
    for (auto u : V[i]) {
      P[u] = i;
    }
    if (P[C[i]] != -1e18) MX[P[C[i]]].push_back(i);
    else X.push_back(i);
    L[i] = P[C[i]];
  }
  for (int i=0; i<n; ++i) P[i] = 1e18;
  for (int i=n-1; i>=0; --i) {
    if (i != n-1) {
      R[i] = P[C[i]];
      if (P[C[i]] != 1e18) MN[P[C[i]]].push_back(i);
      else Y.push_back(i);
    }
    for (auto u : V[i]) {
      P[u] = i;
    }
  }
  for (auto u : X) {
    ++mp[u];
  }
  auto it = mp.lower_bound(0);
  if (it != mp.end()) {
    ST.updateMX(1, 0, n-1, 0, it->first, 0);
  }
  for (ll i=0; i<n-1; ++i) {
    for (auto u : MX[i]) {
      ++mp[u];
    }
    if (R[i] == 1e18) {
      ST.updateMX(1, 0, n-1, i+1, n-1, i+1);
      continue;
    }
    auto it = mp.lower_bound(R[i]);
    if (it != mp.begin()) {
      it = prev(it);
      if (i+1 <= it->first) ST.updateMX(1, 0, n-1, i+1, it->first, i+1);
    }
  }
  mp.clear();
  for (auto u : Y) {
    ++mp[u];
  }
  it = mp.end();
  if (it != mp.begin()) {
    it = prev(it);
    ST.updateMN(1, 0, n-1, it->first+1, n-1, n-1);
  }
  for (ll i=n-1; i>=0; --i) {
    if (i != n-1) {
      if (L[i] == -1e18) {
        ST.updateMN(1, 0, n-1, 0, i, i);
        continue;
      }
      auto it = mp.lower_bound(L[i]);
      if (it != mp.end()) {
        if (it->first+1 <= i) ST.updateMN(1, 0, n-1, it->first+1, i, i);
      }
    }
    for (auto u : MN[i]) {
      ++mp[u];
    }
  }
  cin >> q;
  while (q--) {
    cin >> a >> b;
    --a, --b;
    auto u = ST.query(1, 0, n-1, a);
    if (a <= b) {
      if (b <= u[0]) cout << "YES\n";
      else cout << "NO\n";
    }
    else {
      if (u[1] <= b) cout << "YES\n";
      else cout << "NO\n";
    }
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75