제출 #839454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839454		adaawf	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1577 ms	129012 KiB

selling_rna

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
string s[100005];
multiset<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].insert(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].insert(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].count(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;
}
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] = " " + s[i];
        s[i] = conv(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++) {
        vector<int> v;
        v.push_back(0);
        for (int j = 1; j < s[i].size(); j++) {
            v[j] = v[j - 1] * 5 + (s[i][j] - '0');
            v[j] %= mod;
        }
        for (int j = 1; j < s[i].size(); j++) {
            update(1, 1, n, i, (v[s[i].size() - 1] - v[j - 1] * p[s[i].size() - j] % mod + mod) % mod);
        }
    }
    for (int jj = 0; jj < q; jj++) {
        int l = 1, r = n, h = -1, k = -1, c = 0;
        string s, t;
        cin >> s >> t;
        s = " " + s;
        t = " " + t;
        s = conv(s);
        t = conv(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 (h == -1 || k == -1) cout << 0;
        else {
            cout << sum(1, 1, n, h, k, c);
        }
        cout << '\n';
    }
}

컴파일 시 표준 에러 (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 'std::string conv(std::string)':
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < s.size(); j++) {
      |                     ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 1; j < s[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
selling_rna.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 1; j < s[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
selling_rna.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 1; i < t.size(); i++) {
      |                         ~~^~~~~~~~~~

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