Submission #693097

#	Time	Username	Problem	Language	Result	Execution time	Memory
693097		horiseun	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	341 ms	455048 KiB

selling_rna

#include <iostream>
#include <vector>
#include <tuple>
#include <string>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, m, nx[2][2000005][30], x[2000005], y[2000005], idx1, idx2;
vector<int> v[2000005];
string s[2000005];

void update1(string curr, int pos) {
    int nd = 0;
    for (int i = 0; i < curr.size(); i++) {
        if (!nx[0][nd][curr[i] - 'A']) nx[0][nd][curr[i] - 'A'] = idx1++; 
        x[nd] = min(x[nd], pos);
        y[nd] = max(y[nd], pos);
        nd = nx[0][nd][curr[i] - 'A'];
    }
    x[nd] = min(x[nd], pos);
    y[nd] = max(y[nd], pos);
}

void update2(string curr, int pos) {
    int nd = 0;
    for (int i = curr.size() - 1; i >= 0; i--) {
        if (!nx[1][nd][curr[i] - 'A']) nx[1][nd][curr[i] - 'A'] = idx2++;
        v[nd].push_back(pos);
        nd = nx[1][nd][curr[i] - 'A'];
    }
    v[nd].push_back(pos);
}

pair<int, int> query1(string curr) {
    int nd = 0;
    for (int i = 0; i < curr.size(); i++) {
        if (!nx[0][nd][curr[i] - 'A']) return {-1, -1};
        nd = nx[0][nd][curr[i] - 'A'];
    }
    return {x[nd], y[nd]};
}

int query2(string curr, int l, int r) {
    if (l == -1 || r == -1) return 0;
    int nd = 0;
    for (int i = curr.size() - 1; i >= 0; i--) {
        if (!nx[1][nd][curr[i] - 'A']) return 0;
        nd = nx[1][nd][curr[i] - 'A'];
    }
    return (upper_bound(v[nd].begin(), v[nd].end(), r) - lower_bound(v[nd].begin(), v[nd].end(), l));
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    sort(s, s + n);

    fill(x, x + 2000005, 1e9);
    idx1 = 1, idx2 = 1;
    for (int i = 0; i < n; i++) {
        update1(s[i], i);
        update2(s[i], i);
    }
    for (int i = 0; i < m; i++) {
        string pr, su; cin >> pr >> su;
        pair<int, int> res = query1(pr);
        cout << query2(su, res.f, res.s) << "\n";
    }

}

Compilation message (stderr)

selling_rna.cpp: In function 'void update1(std::string, int)':
selling_rna.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < curr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> query1(std::string)':
selling_rna.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < curr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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