제출 #986082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986082		badont	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	113 ms	146516 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable<    T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>    : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) {  return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) {  cout << "[";  for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", ";  } return cout << "]";}

#ifdef LOCAL
  void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
  #define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #define debug(...) "zzz"
#endif
// clang-format on

using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;

#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

constexpr int A = 4;
struct node {
  int tin, tout;
  array<int, 4> c;
  node() : tin(0), tout(0), c({-1, -1, -1, -1}) {}
};

template <typename T> struct fen {
  vector<T> tr;
  ll mxn;

  fen(ll sz) {
    mxn = sz;
    tr.assign(sz + 5, 0);
  }

  void upd(ll g, T k) {
    g++;
    assert(g != 0);
    for (; g <= mxn; g += g & -g)
      tr[g] += k;
  }

  T ge(ll g) {
    g++;
    T res = 0;
    for (; g; g -= g & -g)
      res += tr[g];
    return res;
  }

  T rng(ll l, ll r) { return ge(r) - ge(l - 1); }
};

constexpr int N = 2e6 + 5;
node p1[N], p2[N];

void solve() {
  // open
  int n, m;
  cin >> n >> m;

  vector<vector<int>> a(n);
  for (auto &u : a) {
    string s;
    cin >> s;
    u.resize(s.size());

    for (int i = 0; i < (int)s.size(); i++) {
      switch (s[i]) {
      case 'A':
        u[i] = 0;
        break;
      case 'C':
        u[i] = 1;
        break;
      case 'G':
        u[i] = 2;
        break;
      case 'U':
        u[i] = 3;
        break;
      };
    }
  }

  vector<vector<int>> fo(m), ba(m);
  for (int i = 0; i < m; i++) {
    string s;
    cin >> s;
    {
      auto &u = fo[i];
      u.resize(s.size());
      for (int i = 0; i < (int)s.size(); i++) {
        switch (s[i]) {
        case 'A':
          u[i] = 0;
          break;
        case 'C':
          u[i] = 1;
          break;
        case 'G':
          u[i] = 2;
          break;
        case 'U':
          u[i] = 3;
          break;
        };
      }
    }
    cin >> s;
    {
      auto &u = ba[i];
      u.resize(s.size());
      for (int i = 0; i < (int)s.size(); i++) {
        switch (s[i]) {
        case 'A':
          u[i] = 0;
          break;
        case 'C':
          u[i] = 1;
          break;
        case 'G':
          u[i] = 2;
          break;
        case 'U':
          u[i] = 3;
          break;
        };
      }
      reverse(all(u));
    }
  }

  int pool_1_nxt = 1, pool_2_nxt = 1;
  for (int i = 0; i < n; i++) {
    debug(i);
    const auto &h = a[i];
    int cur = 0;
    for (const auto u : h) {
      if (p1[cur].c[u] == -1) {
        p1[cur].c[u] = pool_1_nxt++;
      }
      cur = p1[cur].c[u];
    }

    auto hc = h;
    reverse(all(hc));
    cur = 0;
    for (const auto u : hc) {
      if (p2[cur].c[u] == -1) {
        p2[cur].c[u] = pool_2_nxt++;
      }
      cur = p2[cur].c[u];
    }
  }

  int cc = 0;
  auto dfs = [&](auto &dfs, int g, auto pool) -> void {
    pool[g].tin = cc++;
    for (int i = 0; i < 4; i++) {
      if (pool[g].c[i] != -1) {
        dfs(dfs, pool[g].c[i], pool);
      }
    }
    pool[g].tout = cc++;
  };
  dfs(dfs, 0, p1);
  cc = 0;
  dfs(dfs, 0, p2);

  vector<array<int, 4>> range_query(m);
  for (int i = 0; i < m; i++) {
    auto &[l1, r1, l2, r2] = range_query[i];

    int cur = 0;
    for (auto u : fo[i]) {
      if (p1[cur].c[u] == -1) {
        l1 = r1 = -1;
        break;
      }
      cur = p1[cur].c[u];
    }

    if (l1 != -1) {
      l1 = p1[cur].tin;
      r1 = p1[cur].tout;
    }

    cur = 0;
    for (auto u : ba[i]) {
      if (p2[cur].c[u] == -1) {
        l2 = r2 = -1;
        break;
      }
      cur = p2[cur].c[u];
    }

    if (r1 != -1) {
      l2 = p2[cur].tin;
      r2 = p2[cur].tout;
    }
  }

  vector<pii> locations;
  for (int i = 0; i < n; i++) {
    int x = -1, y = -1;
    const auto &h = a[i];
    int cur = 0;
    for (const auto u : h) {
      cur = p1[cur].c[u];
    }

    x = cur;

    auto hc = h;
    cur = 0;
    reverse(all(hc));
    for (const auto u : hc) {
      cur = p2[cur].c[u];
    }
    y = cur;
    locations.pb({x, y});
  }

  int max_x = p1[0].tout + 1;
  vector pt_bin(max_x, vector<int>());
  vector add_bin(max_x, vector<array<int, 3>>());
  vector sub_bin(max_x, vector<array<int, 3>>());

  for (auto [x, y] : locations) {
    pt_bin[x].pb(y);
  }

  for (int i = 0; i < m; i++) {
    const auto [l1, r1, l2, r2] = range_query[i];
    if (l1 != -1 and l2 != -1) {
      if (l1 > 0) {
        sub_bin[l1 - 1].pb({l2, r2, i});
      }
      add_bin[r1].pb({l2, r2, i});
    }
  }

  int max_y = p2[0].tout + 1;
  fen<ll> tree(max_y);
  vector<ll> ans(m);
  for (int x = 0; x < max_x; x++) {
    for (auto y : pt_bin[x]) {
      tree.upd(y, 1);
    }
    for (auto [l, r, qid] : sub_bin[x]) {
      ans[qid] -= tree.rng(l, r);
    }
    for (auto [l, r, qid] : add_bin[x]) {
      ans[qid] += tree.rng(l, r);
    }
  }

  for (auto &u : ans)
    cout << u << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(false);

  ll T = 1;
  // cin >> T;
  for (int t = 0; t < T; t++)
    solve();

  cout.flush();
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
selling_rna.cpp:141:5: note: in expansion of macro 'debug'
  141 |     debug(i);
      |     ^~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40