oj.uz

Submission #974870

# Submission time Handle Problem Language Result Execution time Memory
974870 2024-05-04T04:00:11 Z abczz Long Mansion (JOI17_long_mansion) C++14
20 / 100
 1020 ms 101700 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 76624 KB Output is correct
2 Correct 27 ms 76892 KB Output is correct
3 Correct 30 ms 77148 KB Output is correct
4 Correct 28 ms 76792 KB Output is correct
5 Correct 25 ms 76636 KB Output is correct
6 Correct 26 ms 76888 KB Output is correct
7 Correct 27 ms 76636 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 76624 KB Output is correct
2 Correct 27 ms 76892 KB Output is correct
3 Correct 30 ms 77148 KB Output is correct
4 Correct 28 ms 76792 KB Output is correct
5 Correct 25 ms 76636 KB Output is correct
6 Correct 26 ms 76888 KB Output is correct
7 Correct 27 ms 76636 KB Output is correct
8 Correct 793 ms 82500 KB Output is correct
9 Correct 828 ms 82636 KB Output is correct
10 Correct 836 ms 83048 KB Output is correct
11 Correct 836 ms 83512 KB Output is correct
12 Correct 776 ms 82120 KB Output is correct
13 Correct 778 ms 83040 KB Output is correct
14 Correct 789 ms 82760 KB Output is correct
15 Correct 842 ms 82900 KB Output is correct
16 Correct 775 ms 82672 KB Output is correct
17 Correct 778 ms 82680 KB Output is correct
18 Incorrect 791 ms 82880 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 101660 KB Output is correct
2 Correct 989 ms 101600 KB Output is correct
3 Correct 965 ms 101456 KB Output is correct
4 Correct 1002 ms 101700 KB Output is correct
5 Correct 1020 ms 101644 KB Output is correct
6 Correct 915 ms 99576 KB Output is correct
7 Correct 919 ms 100176 KB Output is correct
8 Correct 931 ms 99952 KB Output is correct
9 Correct 961 ms 99816 KB Output is correct
10 Correct 921 ms 100072 KB Output is correct
11 Correct 912 ms 99880 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 76624 KB Output is correct
2 Correct 27 ms 76892 KB Output is correct
3 Correct 30 ms 77148 KB Output is correct
4 Correct 28 ms 76792 KB Output is correct
5 Correct 25 ms 76636 KB Output is correct
6 Correct 26 ms 76888 KB Output is correct
7 Correct 27 ms 76636 KB Output is correct
8 Correct 793 ms 82500 KB Output is correct
9 Correct 828 ms 82636 KB Output is correct
10 Correct 836 ms 83048 KB Output is correct
11 Correct 836 ms 83512 KB Output is correct
12 Correct 776 ms 82120 KB Output is correct
13 Correct 778 ms 83040 KB Output is correct
14 Correct 789 ms 82760 KB Output is correct
15 Correct 842 ms 82900 KB Output is correct
16 Correct 775 ms 82672 KB Output is correct
17 Correct 778 ms 82680 KB Output is correct
18 Incorrect 791 ms 82880 KB Output isn't correct
19 Halted 0 ms 0 KB -