Submission #839468

#	Time	Username	Problem	Language	Result	Execution time	Memory
839468		adaawf	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1600 ms	337940 KiB

selling_rna

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
string s[200005];
unordered_map<int, int> t[400005];
long long int a[100005], p[400005], mod = 1e9 + 7;
void update(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t[v][y]++;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v][y]++;
}
int sum(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v][x];
    }
    int mid = (tl + tr) / 2;
    return sum(v * 2, tl, mid, l, min(r, mid), x) + sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
}
bool check(int x, string t) {
    for (int i = 1; i < min(t.size(), s[x].size()); i++) {
        if (s[x][i] > t[i]) return true;
        if (s[x][i] < t[i]) return false;
    }
    return true;
}
bool check2(int x, string t) {
    for (int i = 1; i < min(t.size(), s[x].size()); i++) {
        if (s[x][i] < t[i]) return true;
        if (s[x][i] > t[i]) return false;
    }
    return true;
}
bool check3(int x, string t) {
    for (int i = 1; i < min(t.size(), s[x].size()); i++) {
        if (s[x][i] != t[i]) return false;
    }
    if (s[x].size() < t.size()) return false;
    return true;
}
string conv(string s) {
    for (int j = 0; j < s.size(); j++) {
        if (s[j] == 'A') s[j] = '1';
        else if (s[j] == 'C') s[j] = '2';
        else if (s[j] == 'G') s[j] = '3';
        else s[j] = '4';
    }
    return s;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = conv(s[i]);
        s[i] = " " + s[i];
    }
    for (int i = 1; i <= 100000; i++) {
        p[i] = p[i - 1] * 5 % mod;
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = s[i].size() - 1;
        vector<long long int> vv;
        vv.push_back(0);
        for (int j = 1; j <= a[i]; j++) {
            vv.push_back((1ll * vv[j - 1] * 5 + (s[i][j] - '0')) % mod);
        }
        for (int j = 1; j <= a[i]; j++) {
            long long int h = (vv[a[i]] - vv[j - 1] * p[a[i] - j + 1] % mod + mod) % mod;
            update(1, 1, n, i, h);
        }
    }
    for (int jj = 0; jj < q; jj++) {
        long long int l = 1, r = n, h = -1, k = -1, c = 0;
        string s, t;
        cin >> s >> t;
        s = conv(s);
        t = conv(t);
        s = " " + s;
        t = " " + t;
        for (int i = 1; i < t.size(); i++) {
            c = (c * 5 + (t[i] - '0')) % mod;
        }
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid, s) == true) {
                r = mid - 1;
                h = mid;
            }
            else l = mid + 1;
        }
        l = 1, r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check2(mid, s) == true) {
                l = mid + 1;
                k = mid;
            }
            else r = mid - 1;
        }
        if (!check3(h, s) || !check3(k, s)) cout << 0;
        else {
            cout << sum(1, 1, n, h, k, c);
        }
        cout << '\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'bool check(int, std::string)':
selling_rna.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   28 |     for (int i = 1; i < min(t.size(), s[x].size()); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool check2(int, std::string)':
selling_rna.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   35 |     for (int i = 1; i < min(t.size(), s[x].size()); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool check3(int, std::string)':
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   42 |     for (int i = 1; i < min(t.size(), s[x].size()); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::string conv(std::string)':
selling_rna.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int j = 0; j < s.size(); j++) {
      |                     ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 1; i < t.size(); i++) {
      |                         ~~^~~~~~~~~~

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