oj.uz

답안 #256816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256816 2020-08-03T08:54:38 Z fedoseevtimofey Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 54136 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> c(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> c[i];
    --c[i];
  }
  vector <set <int>> who(n);
  vector <set <int>> where(n);
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int x;
      cin >> x;
      --x;
      who[i].insert(x);
      where[x].insert(i);
    }
  }
  auto have = [&] (int l, int r, int x) {
    auto it = where[x].lower_bound(l);
    return (it != where[x].end() && (*it) <= r);
  };
  auto adjust = [&] (int l, int r) {
    while (true) {
      if (l > 0 && have(l, r, c[l - 1])) {
        --l;
      } else if (r + 1 < n && have(l, r, c[r])) {
        ++r;
      } else {
        break;
      }
    }
    return make_pair(l, r);
  };
  vector <int> goR(n, -1);
  goR[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    goR[i] = i;
    while (goR[i] + 1 < n && have(i, goR[i], c[goR[i]])) {
      ++goR[i]; 
      goR[i] = max(goR[i], goR[goR[i]]);
    }
  }
  vector <pair <int, int>> go(n);
  go[0] = {0, goR[0]};
  for (int i = 1; i < n; ++i) {
    int j = goR[i];
    int need = c[i - 1];
    if (have(i, j, need)) {
      go[i] = go[i - 1];
      go[i].second = max(go[i].second, goR[i]);
    } else {
      go[i] = {i, goR[i]};
    }
    go[i] = adjust(go[i].first, go[i].second);
  }
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    if (go[x].first <= y && y <= go[x].second) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }   
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 41 ms 1152 KB Output is correct
3 Correct 175 ms 1408 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 952 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 41 ms 1152 KB Output is correct
3 Correct 175 ms 1408 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 952 KB Output is correct
8 Correct 118 ms 3704 KB Output is correct
9 Correct 109 ms 3588 KB Output is correct
10 Correct 148 ms 3832 KB Output is correct
11 Correct 250 ms 4216 KB Output is correct
12 Correct 104 ms 3632 KB Output is correct
13 Correct 107 ms 3704 KB Output is correct
14 Correct 100 ms 3704 KB Output is correct
15 Correct 102 ms 3832 KB Output is correct
16 Correct 103 ms 3964 KB Output is correct
17 Correct 108 ms 7036 KB Output is correct
18 Correct 108 ms 7028 KB Output is correct
19 Correct 113 ms 7212 KB Output is correct
20 Correct 106 ms 7032 KB Output is correct
21 Correct 105 ms 6776 KB Output is correct
22 Correct 109 ms 6948 KB Output is correct
23 Correct 113 ms 6692 KB Output is correct
24 Correct 112 ms 6652 KB Output is correct
25 Correct 134 ms 6776 KB Output is correct
26 Correct 112 ms 6648 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3094 ms 54136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 41 ms 1152 KB Output is correct
3 Correct 175 ms 1408 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 952 KB Output is correct
8 Correct 118 ms 3704 KB Output is correct
9 Correct 109 ms 3588 KB Output is correct
10 Correct 148 ms 3832 KB Output is correct
11 Correct 250 ms 4216 KB Output is correct
12 Correct 104 ms 3632 KB Output is correct
13 Correct 107 ms 3704 KB Output is correct
14 Correct 100 ms 3704 KB Output is correct
15 Correct 102 ms 3832 KB Output is correct
16 Correct 103 ms 3964 KB Output is correct
17 Correct 108 ms 7036 KB Output is correct
18 Correct 108 ms 7028 KB Output is correct
19 Correct 113 ms 7212 KB Output is correct
20 Correct 106 ms 7032 KB Output is correct
21 Correct 105 ms 6776 KB Output is correct
22 Correct 109 ms 6948 KB Output is correct
23 Correct 113 ms 6692 KB Output is correct
24 Correct 112 ms 6652 KB Output is correct
25 Correct 134 ms 6776 KB Output is correct
26 Correct 112 ms 6648 KB Output is correct
27 Execution timed out 3094 ms 54136 KB Time limit exceeded
28 Halted 0 ms 0 KB -