oj.uz

Submission #342880

# Submission time Handle Problem Language Result Execution time Memory
342880 2021-01-03T06:16:56 Z KoD Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 365 ms 169544 KB 
#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 15 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

template <class T>
using Vec = std::vector<T>;

constexpr usize match(const char c) {
  if (c == 'A') return 0;
  if (c == 'G') return 1;
  if (c == 'C') return 2;
  if (c == 'U') return 3;
  return 4;
}

struct Node {
  std::array<usize, 4> next{};
  Vec<usize> idx;
};

usize next(Vec<Node> &trie, const usize u, const usize k) {
  if (trie[u].next[k] == 0) {
    const auto n = trie.size();
    trie.push_back(Node {});
    trie[u].next[k] = n;
  }
  return trie[u].next[k];
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  usize N, M;
  std::cin >> N >> M;
  Vec<std::string> S(N);
  for (auto &x: S) {
    std::cin >> x;
    std::reverse(x.begin(), x.end());
  }
  std::sort(S.begin(), S.end());
  Vec<Node> front;
  front.push_back(Node {});
  for (auto i: range(0, N)) {
    usize pf = 0;
    for (auto j: range(0, S[i].size())) {
      pf = next(front, pf, match(S[i][S[i].size() - j - 1]));
      front[pf].idx.push_back(i);
    }
  }
  while (M--) {
    std::string P, Q;
    std::cin >> P >> Q;
    usize pf = 0;
    for (auto i: range(0, P.size())) {
      pf = next(front, pf, match(P[i]));
    }
    if (front[pf].idx.empty()) {
      std::cout << 0 << '\n';
      continue;
    }
    std::reverse(Q.begin(), Q.end());
    const auto low = [&]() -> usize {
      if (S[front[pf].idx.front()] >= Q) {
        return 0;
      }
      usize ok = front[pf].idx.size(), ng = 0;
      while (ok - ng > 1) {
        const auto md = (ok + ng) / 2;
        if (S[front[pf].idx[md]] >= Q) {
          ok = md;
        }
        else {
          ng = md;
        }
      }
      return ok;
    }();
    const auto high = [&]() -> usize {
      if (S[front[pf].idx.front()].substr(0, Q.size()) > Q) {
        return 0;
      }
      usize ok = front[pf].idx.size(), ng = 0;
      while (ok - ng > 1) {
        const auto md = (ok + ng) / 2;
        if (S[front[pf].idx[md]].substr(0, Q.size()) > Q) {
          ok = md;
        }
        else {
          ng = md;
        }
      }
      return ok;
    }();
    std::cout << high - low << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 25216 KB Output is correct
2 Correct 85 ms 23816 KB Output is correct
3 Correct 365 ms 169544 KB Output is correct
4 Correct 314 ms 161736 KB Output is correct
5 Correct 231 ms 149796 KB Output is correct
6 Correct 233 ms 149792 KB Output is correct
7 Correct 73 ms 17900 KB Output is correct
8 Correct 220 ms 80628 KB Output is correct
9 Correct 188 ms 84056 KB Output is correct
10 Correct 166 ms 88456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3172 KB Output is correct
2 Correct 41 ms 2540 KB Output is correct
3 Correct 50 ms 3304 KB Output is correct
4 Correct 30 ms 3048 KB Output is correct
5 Correct 35 ms 3180 KB Output is correct
6 Correct 45 ms 3436 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 91 ms 25216 KB Output is correct
9 Correct 85 ms 23816 KB Output is correct
10 Correct 365 ms 169544 KB Output is correct
11 Correct 314 ms 161736 KB Output is correct
12 Correct 231 ms 149796 KB Output is correct
13 Correct 233 ms 149792 KB Output is correct
14 Correct 73 ms 17900 KB Output is correct
15 Correct 220 ms 80628 KB Output is correct
16 Correct 188 ms 84056 KB Output is correct
17 Correct 166 ms 88456 KB Output is correct
18 Correct 41 ms 3172 KB Output is correct
19 Correct 41 ms 2540 KB Output is correct
20 Correct 50 ms 3304 KB Output is correct
21 Correct 30 ms 3048 KB Output is correct
22 Correct 35 ms 3180 KB Output is correct
23 Correct 45 ms 3436 KB Output is correct
24 Correct 107 ms 27332 KB Output is correct
25 Correct 147 ms 27716 KB Output is correct
26 Correct 108 ms 27332 KB Output is correct
27 Correct 320 ms 153920 KB Output is correct
28 Correct 315 ms 29828 KB Output is correct
29 Correct 117 ms 16852 KB Output is correct