Submission #553397

#	Time	Username	Problem	Language	Result	Execution time	Memory
553397		RaresFelix	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	1603 ms	40160 KiB

selling_rna

#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 == '~' ? 5 : v == 'U' ? 4 : v == 'G' ? 3 : v == 'C' ? 2 : v == 'A';
}

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, -1});
    }
    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];
        V.push_back({p + "#", i});
        V.push_back({p + "~", i});
    }
    auto sort_level = [&](int p) {
        V2.resize(V.size());
        vector<int> Fr(6, 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 == -1) {
            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 (stderr)

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

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