oj.uz

Submission #986088

# Submission time Handle Problem Language Result Execution time Memory
986088 2024-05-19T17:51:13 Z badont Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 197 ms 387664 KB 
#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 = p1[cur].tin;

    auto hc = h;
    cur = 0;
    reverse(all(hc));
    for (const auto u : hc) {
      cur = p2[cur].c[u];
    }
    y = p2[cur].tin;
    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;
}

Compilation message

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 94300 KB Output is correct
2 Correct 18 ms 94400 KB Output is correct
3 Correct 18 ms 94308 KB Output is correct
4 Correct 18 ms 94312 KB Output is correct
5 Correct 18 ms 94300 KB Output is correct
6 Correct 18 ms 94300 KB Output is correct
7 Correct 18 ms 94296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 142468 KB Output is correct
2 Correct 108 ms 145316 KB Output is correct
3 Correct 197 ms 387664 KB Output is correct
4 Correct 188 ms 374508 KB Output is correct
5 Correct 184 ms 298232 KB Output is correct
6 Correct 183 ms 301136 KB Output is correct
7 Correct 73 ms 122448 KB Output is correct
8 Correct 141 ms 236884 KB Output is correct
9 Correct 136 ms 217684 KB Output is correct
10 Correct 109 ms 203920 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 106696 KB Output is correct
2 Correct 38 ms 102724 KB Output is correct
3 Correct 42 ms 105164 KB Output is correct
4 Correct 35 ms 102856 KB Output is correct
5 Correct 36 ms 102828 KB Output is correct
6 Correct 42 ms 104916 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 94300 KB Output is correct
2 Correct 18 ms 94400 KB Output is correct
3 Correct 18 ms 94308 KB Output is correct
4 Correct 18 ms 94312 KB Output is correct
5 Correct 18 ms 94300 KB Output is correct
6 Correct 18 ms 94300 KB Output is correct
7 Correct 18 ms 94296 KB Output is correct
8 Correct 110 ms 142468 KB Output is correct
9 Correct 108 ms 145316 KB Output is correct
10 Correct 197 ms 387664 KB Output is correct
11 Correct 188 ms 374508 KB Output is correct
12 Correct 184 ms 298232 KB Output is correct
13 Correct 183 ms 301136 KB Output is correct
14 Correct 73 ms 122448 KB Output is correct
15 Correct 141 ms 236884 KB Output is correct
16 Correct 136 ms 217684 KB Output is correct
17 Correct 109 ms 203920 KB Output is correct
18 Correct 43 ms 106696 KB Output is correct
19 Correct 38 ms 102724 KB Output is correct
20 Correct 42 ms 105164 KB Output is correct
21 Correct 35 ms 102856 KB Output is correct
22 Correct 36 ms 102828 KB Output is correct
23 Correct 42 ms 104916 KB Output is correct
24 Correct 112 ms 144568 KB Output is correct
25 Correct 123 ms 149196 KB Output is correct
26 Correct 102 ms 142288 KB Output is correct
27 Correct 180 ms 340172 KB Output is correct
28 Correct 150 ms 140336 KB Output is correct
29 Correct 88 ms 126660 KB Output is correct