oj.uz

Submission #256810

# Submission time Handle Problem Language Result Execution time Memory
256810 2020-08-03T08:49:54 Z fedoseevtimofey Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 52996 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);
    }
  }
  vector <int> goR(n, -1);
  goR[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    if (who[i].count(c[i])) goR[i] = goR[i + 1];
    else goR[i] = 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 <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);
  }*/
  for (int i = 0; i < n; ++i) {
    go[i] = adjust(i, i);
  }
  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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 88 ms 1144 KB Output is correct
3 Correct 521 ms 1416 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 96 ms 972 KB Output is correct
6 Correct 18 ms 896 KB Output is correct
7 Correct 11 ms 768 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 88 ms 1144 KB Output is correct
3 Correct 521 ms 1416 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 96 ms 972 KB Output is correct
6 Correct 18 ms 896 KB Output is correct
7 Correct 11 ms 768 KB Output is correct
8 Correct 129 ms 2604 KB Output is correct
9 Correct 127 ms 2552 KB Output is correct
10 Correct 193 ms 2808 KB Output is correct
11 Correct 558 ms 3204 KB Output is correct
12 Correct 129 ms 2560 KB Output is correct
13 Correct 117 ms 2680 KB Output is correct
14 Correct 111 ms 2680 KB Output is correct
15 Correct 151 ms 2756 KB Output is correct
16 Correct 191 ms 2936 KB Output is correct
17 Correct 119 ms 7032 KB Output is correct
18 Correct 137 ms 7084 KB Output is correct
19 Correct 170 ms 7104 KB Output is correct
20 Correct 182 ms 7032 KB Output is correct
21 Correct 197 ms 6776 KB Output is correct
22 Correct 139 ms 6904 KB Output is correct
23 Correct 130 ms 6780 KB Output is correct
24 Correct 121 ms 6648 KB Output is correct
25 Correct 122 ms 6688 KB Output is correct
26 Correct 126 ms 6692 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 52996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 88 ms 1144 KB Output is correct
3 Correct 521 ms 1416 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 96 ms 972 KB Output is correct
6 Correct 18 ms 896 KB Output is correct
7 Correct 11 ms 768 KB Output is correct
8 Correct 129 ms 2604 KB Output is correct
9 Correct 127 ms 2552 KB Output is correct
10 Correct 193 ms 2808 KB Output is correct
11 Correct 558 ms 3204 KB Output is correct
12 Correct 129 ms 2560 KB Output is correct
13 Correct 117 ms 2680 KB Output is correct
14 Correct 111 ms 2680 KB Output is correct
15 Correct 151 ms 2756 KB Output is correct
16 Correct 191 ms 2936 KB Output is correct
17 Correct 119 ms 7032 KB Output is correct
18 Correct 137 ms 7084 KB Output is correct
19 Correct 170 ms 7104 KB Output is correct
20 Correct 182 ms 7032 KB Output is correct
21 Correct 197 ms 6776 KB Output is correct
22 Correct 139 ms 6904 KB Output is correct
23 Correct 130 ms 6780 KB Output is correct
24 Correct 121 ms 6648 KB Output is correct
25 Correct 122 ms 6688 KB Output is correct
26 Correct 126 ms 6692 KB Output is correct
27 Execution timed out 3061 ms 52996 KB Time limit exceeded
28 Halted 0 ms 0 KB -