Submission #752799

#	Time	Username	Problem	Language	Result	Execution time	Memory
752799		racsosabe	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	154 ms	115212 KiB

selling_rna

#include<bits/stdc++.h>
using namespace::std;
 
const int N = 100000 + 5;
const int SUML = 2000000 + 5;
const int E = 4;
const string alphabet = "AGCU";

int id(char c) {
    for(int i = 0; i < alphabet.size(); i++) {
        if(alphabet[i] == c) return i;
    }
    assert(false);
}

int n;
int m;
int T;
int nodes;
int res[N];
string s[N];
string Q[N];
int in[SUML];
int out[SUML];
int sorted[N];
int frec[SUML];
int trie[E][SUML];
vector<int> ids[SUML];
vector<int> pending[N];

void add_node() {
    for(int i = 0; i < E; i++) trie[i][nodes] = 0;
    frec[nodes] = 0;
    ids[nodes].clear();
    nodes += 1;
}

void insert(string &s, int to) {
    int pos = 0;
    for(int i = 0; i < s.size(); i++) {
        int c = id(s[i]);
        if(trie[c][pos] == 0) {
            trie[c][pos] = nodes;
            add_node();
        }
        pos = trie[c][pos];
        frec[pos] += 1;
    }
    ids[pos].emplace_back(to);
}

void sort_strings(int u = 0) {
    in[u] = T;
    for(auto x : ids[u]) {
        sorted[T++] = x;
    }
    for(int c = 0; c < E; c++) {
        if(!trie[c][u]) continue;
        sort_strings(trie[c][u]);
    }
    out[u] = T - 1;
}

int query(string &s) {
    int pos = 0;
    for(int i = 0; i < s.size(); i++) {
        int c = id(s[i]);
        if(!trie[c][pos]) return 0;
        pos = trie[c][pos];
    }
    return frec[pos];
}

void solve() {
    nodes = 0;
    add_node();
    for(int i = 0; i < n; i++) {
        insert(s[sorted[i]], i);
        for(auto to : pending[i]) {
            if(to < 0) {
                res[-to] -= query(Q[-to]);
            }
            else { 
                res[to] += query(Q[to]);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    nodes = 1;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i], i);
    }
    sort_strings();
    for(int i = 1; i <= m; i++) {
        string P;
        cin >> P >> Q[i];
        reverse(Q[i].begin(), Q[i].end());
        int pos = 0;
        for(int j = 0; j < P.size(); j++) {
            int c = id(P[j]);
            if(!trie[c][pos]) {
                pos = -1;
                break;
            }
            pos = trie[c][pos];
        }
        if(~pos) {
            if(in[pos]) pending[in[pos] - 1].emplace_back(-i);
            pending[out[pos]].emplace_back(i);
        }
    }
    for(int i = 1; i <= n; i++) reverse(s[i].begin(), s[i].end());
    solve();
    for(int i = 1; i <= m; i++) cout << res[i] << '\n';
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int id(char)':
selling_rna.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < alphabet.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert(std::string&, int)':
selling_rna.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int query(std::string&)':
selling_rna.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j = 0; j < P.size(); j++) {
      |                        ~~^~~~~~~~~~

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