oj.uz

Submission #256820

# Submission time Handle Problem Language Result Execution time Memory
256820 2020-08-03T08:56:19 Z fedoseevtimofey Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 52984 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]]);
    }
  }
  assert((double)clock() / CLOCKS_PER_SEC < 1);
  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]);
      go[i] = adjust(go[i].first, go[i].second);
    } else {
      go[i] = {i, goR[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 5 ms 1024 KB Output is correct
2 Correct 41 ms 1148 KB Output is correct
3 Correct 180 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 768 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 41 ms 1148 KB Output is correct
3 Correct 180 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 120 ms 2688 KB Output is correct
9 Correct 115 ms 2552 KB Output is correct
10 Correct 151 ms 2808 KB Output is correct
11 Correct 265 ms 3208 KB Output is correct
12 Correct 104 ms 2552 KB Output is correct
13 Correct 113 ms 2680 KB Output is correct
14 Correct 108 ms 2680 KB Output is correct
15 Correct 110 ms 2680 KB Output is correct
16 Correct 105 ms 3064 KB Output is correct
17 Correct 110 ms 2680 KB Output is correct
18 Correct 105 ms 2680 KB Output is correct
19 Correct 106 ms 2808 KB Output is correct
20 Correct 110 ms 2808 KB Output is correct
21 Correct 104 ms 2940 KB Output is correct
22 Correct 115 ms 2808 KB Output is correct
23 Correct 107 ms 2424 KB Output is correct
24 Correct 125 ms 2424 KB Output is correct
25 Correct 111 ms 2424 KB Output is correct
26 Correct 107 ms 2296 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 41 ms 1148 KB Output is correct
3 Correct 180 ms 1528 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 120 ms 2688 KB Output is correct
9 Correct 115 ms 2552 KB Output is correct
10 Correct 151 ms 2808 KB Output is correct
11 Correct 265 ms 3208 KB Output is correct
12 Correct 104 ms 2552 KB Output is correct
13 Correct 113 ms 2680 KB Output is correct
14 Correct 108 ms 2680 KB Output is correct
15 Correct 110 ms 2680 KB Output is correct
16 Correct 105 ms 3064 KB Output is correct
17 Correct 110 ms 2680 KB Output is correct
18 Correct 105 ms 2680 KB Output is correct
19 Correct 106 ms 2808 KB Output is correct
20 Correct 110 ms 2808 KB Output is correct
21 Correct 104 ms 2940 KB Output is correct
22 Correct 115 ms 2808 KB Output is correct
23 Correct 107 ms 2424 KB Output is correct
24 Correct 125 ms 2424 KB Output is correct
25 Correct 111 ms 2424 KB Output is correct
26 Correct 107 ms 2296 KB Output is correct
27 Execution timed out 3061 ms 52984 KB Time limit exceeded
28 Halted 0 ms 0 KB -