oj.uz

Submission #256808

# Submission time Handle Problem Language Result Execution time Memory
256808 2020-08-03T08:47:16 Z fedoseevtimofey Long Mansion (JOI17_long_mansion) C++14
5 / 100
 3000 ms 54904 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);
  }
  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 54 ms 1152 KB Output is correct
3 Correct 209 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 54 ms 1152 KB Output is correct
3 Correct 209 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 126 ms 6904 KB Output is correct
9 Correct 125 ms 6896 KB Output is correct
10 Correct 153 ms 7416 KB Output is correct
11 Correct 281 ms 7932 KB Output is correct
12 Correct 130 ms 6392 KB Output is correct
13 Correct 112 ms 7032 KB Output is correct
14 Correct 122 ms 7032 KB Output is correct
15 Correct 113 ms 7032 KB Output is correct
16 Incorrect 108 ms 6776 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 54904 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 54 ms 1152 KB Output is correct
3 Correct 209 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 126 ms 6904 KB Output is correct
9 Correct 125 ms 6896 KB Output is correct
10 Correct 153 ms 7416 KB Output is correct
11 Correct 281 ms 7932 KB Output is correct
12 Correct 130 ms 6392 KB Output is correct
13 Correct 112 ms 7032 KB Output is correct
14 Correct 122 ms 7032 KB Output is correct
15 Correct 113 ms 7032 KB Output is correct
16 Incorrect 108 ms 6776 KB Output isn't correct
17 Halted 0 ms 0 KB -