Submission #553404

#	Time	Username	Problem	Language	Result	Execution time	Memory
553404		RaresFelix	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1436 ms	1048576 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 == '~' ? 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;
    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];
        len_ma = max(len_ma, int(p.size()));
        V.push_back({p + "$", i});
        V.push_back({p + "~", i});
    }
    vector<int> OrdV, O2;
    for(int i = 0; i < V.size(); ++i) OrdV.push_back(i);
    auto sort_level = [&](int p) {
        O2.resize(V.size());
        vector<int> Fr(7, 0);
        for(auto &it : OrdV)
            ++Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])];
        for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
        reverse(OrdV.begin(), OrdV.end());
        for(auto &it : OrdV)
            O2[--Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])]] = it;
        swap(O2, OrdV);
    };
    for(int i = len_ma; i >= 0; --i)
        sort_level(i);
    int nrw = 0;
    for(auto it : OrdV) {
        auto &[w, id] = V[it];
        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 function 'int main()':
selling_rna.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0; i < V.size(); ++i) OrdV.push_back(i);
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In lambda function:
selling_rna.cpp:87:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |             ++Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])];
      |                   ~~~~~~~~~~~~~~~~~~~^~~~
selling_rna.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = 1; i < Fr.size(); ++i) Fr[i] += Fr[i-1];
      |                        ~~^~~~~~~~~~~
selling_rna.cpp:91:41: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |             O2[--Fr[(V[it].first.size() <= p) ? 0 : sort_id(V[it].first[p])]] = it;
      |                      ~~~~~~~~~~~~~~~~~~~^~~~

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