oj.uz

Submission #553403

# Submission time Handle Problem Language Result Execution time Memory
553403 2022-04-25T18:30:46 Z RaresFelix Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 40664 KB 
#include <bits/stdc++.h>
#define MN 100071

using namespace std;

int n, m;

static inline int nr_lit(const char &v) {
    return v == 'U' ? 3 : v == 'G' ? 2 : v == 'C';
}
static inline int sort_id(const char &v) {
    return v == '~' ? 6 : v == 'U' ? 5 : v == 'G' ? 4 : v == 'C' ? 3 : v == 'A' ? 2 : v == '#';
}

struct trie {
    struct nod {
        int nr;
        nod* fii[4];
    };
    using ns = nod*;
    ns root;
    trie() {
        root = new nod{0, {0, 0, 0, 0}};
    }
    void add(const string &word) {
        ns p = root;
        p->nr++;
        for(auto it : word) {
            if(!p->fii[nr_lit(it)]) {
                p->fii[nr_lit(it)] = new nod{0, {0, 0, 0, 0}};
            }
            p = p->fii[nr_lit(it)];
            p->nr++;
        }
    }
    int count(const string &word) {
        ns p = root;
        for(auto it : word)
            if(!p->fii[nr_lit(it)]) return 0;
            else p = p->fii[nr_lit(it)];
        return p->nr;
    }
};

namespace AINT {
    trie V[4 * MN];
    void add_string(int p, string &v, int u = 1, int s = 1, int d = n) {
        if(d < p || p < s) return;
        V[u].add(v);
        if(s == d) return;
        add_string(p, v, u << 1, s, (s + d) >> 1);
        add_string(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
    }
    int query(int l, int r, string &v, int u = 1, int s = 1, int d = n) {
        if(r < s || d < l) return 0;
        if(l <= s && d <= r) return V[u].count(v);
        return query(l, r, v, u << 1, s, (s + d) >> 1) + query(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int len_ma = 0;
    cin >> n >> m;
    vector<pair<string, int> > V, V2;
    for(int i = 1; i <= n; ++i) {
        string v;
        cin >> v; len_ma = max(len_ma, (int)v.size());
        v += '#';
        V.push_back({v, n});
    }
    vector<int> R(m), St(m), Dr(m);
    vector<string> Q(m);
    for(int i = 0; i < m; ++i) {
        string p;
        cin >> p >> Q[i];
        len_ma = max(len_ma, int(p.size()));
        V.push_back({p + "$", i});
        V.push_back({p + "~", i});
    }
    auto sort_level = [&](int p) {
        V2.resize(V.size());
        vector<int> Fr(7, 0);
        for(auto &[w, id] : V) {
            ++Fr[(w.size() <= p) ? 0 : sort_id(w[p])];
        }
        for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
        reverse(V.begin(), V.end());
        for(auto it : V)
            V2[--Fr[(it.first.size() <= p) ? 0 : sort_id(it.first[p])]] = it;
        V = move(V2);
        V2.clear();
    };
    for(int i = len_ma; i >= 0; --i)
        sort_level(i);
    int nrw = 0;
    for(auto &[w, id] : V) {
        if(id == n) {
            w.resize(w.size() - 1);
            reverse(w.begin(), w.end());
            AINT::add_string(++nrw, w);
        }
        else {
            if(!St[id]) St[id] = nrw + 1;
            Dr[id] = nrw;
        }
    }
    for(int i = 0; i < m; ++i) {
        reverse(Q[i].begin(), Q[i].end());
        R[i] = AINT::query(St[i], Dr[i], Q[i]);
    }
    for(auto it : R) cout << it << "\n";
    return 0;
}

Compilation message

selling_rna.cpp: In lambda function:
selling_rna.cpp:85:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |             ++Fr[(w.size() <= p) ? 0 : sort_id(w[p])];
      |                   ~~~~~~~~~^~~~
selling_rna.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
      |                        ~~^~~~~~~~~~~
selling_rna.cpp:90:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |             V2[--Fr[(it.first.size() <= p) ? 0 : sort_id(it.first[p])]] = it;
      |                      ~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22228 KB Output is correct
2 Correct 18 ms 22228 KB Output is correct
3 Correct 18 ms 22344 KB Output is correct
4 Correct 17 ms 22248 KB Output is correct
5 Correct 18 ms 22256 KB Output is correct
6 Correct 17 ms 22248 KB Output is correct
7 Correct 16 ms 22316 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 39852 KB Output is correct
2 Correct 108 ms 40596 KB Output is correct
3 Correct 123 ms 40664 KB Output is correct
4 Correct 75 ms 37484 KB Output is correct
5 Correct 105 ms 38452 KB Output is correct
6 Correct 127 ms 39660 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22228 KB Output is correct
2 Correct 18 ms 22228 KB Output is correct
3 Correct 18 ms 22344 KB Output is correct
4 Correct 17 ms 22248 KB Output is correct
5 Correct 18 ms 22256 KB Output is correct
6 Correct 17 ms 22248 KB Output is correct
7 Correct 16 ms 22316 KB Output is correct
8 Execution timed out 1588 ms 38664 KB Time limit exceeded
9 Halted 0 ms 0 KB -