제출 #1070504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1070504		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	89 ms	117844 KiB

selling_rna

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
using lli = long long;
const int maxN = 1e5 + 5;
const int maxS = 2e6 + 5;
const int maxA = 4;
int tr[maxS][maxA],cnt,h[maxS];
string q[maxN],s[maxN],p[maxN],s1[maxN];
int n,m,idn[maxN],idm[maxN],res[maxN];
int tk(char c)
{
    if (c == 'G') return 0;
    if (c == 'U') return 1;
    if (c == 'C') return 2;
    if (c == 'A') return 3;
}
void add(string s)
{
    int node = 0;
    for (char c : s)
    {
        if (tr[node][tk(c)] == 0) tr[node][tk(c)] = ++cnt;
        node = tr[node][tk(c)];
        h[node]++;
    }
}
void del(const string& s)
{
    int node = 0;
    for (char c : s)
    {
        int pos = node;
        node = tr[node][tk(c)];
        h[node]--;
        if (h[node] == 0) tr[pos][tk(c)] = 0;
    }
}
int calc(const string& s)
{
    int node = 0;
    for (char c : s)
    {
        if (tr[node][tk(c)] == 0) return 0;
        node = tr[node][tk(c)];
    }
    return h[node];
}
bool cmp(const int& a,const int& b)
{
    return s[a] < s[b];
}
bool cmp1(const int& a,const int& b)
{
    return p[a] < p[b];
}
void input()
{
    cnt = 0;
    cin >> n >> m;
    for (int i = 1;i <= n;++i)
    {
        cin >> s[i];
        idn[i] = i;
    }
    for (int i = 1;i <= m;++i)
    {
        idm[i] = i;
        cin >> p[i] >> q[i];
        reverse(q[i].begin(),q[i].end());
    }
    sort(idn + 1,idn + n + 1,cmp);
    sort(idm + 1,idm + m + 1,cmp1);
}
bool check(const string& b,const string& a)
{
    if (a.size() > b.size()) return false;
    for (int i = 0;i < a.size();++i)
        if (a[i] != b[i]) return false;
    return true;
}
void solve()
{
    for (int i = 1;i <= n;++i)
    {
        reverse(s[i].begin(),s[i].end());
        s1[i] = s[i];
        reverse(s[i].begin(),s[i].end());
    }
    int l = 1,r = 0;
    for (int i = 1;i <= m;++i)
    {
        while (l <= n && p[idm[i]] > s[idn[l]] && !check(s[idn[l]],p[idm[i]]))
        {
            if (l <= r) del(s1[idn[l]]);
            ++l;
        }
        r = max(l - 1,r);
        while (r + 1 <= n && check(s[idn[r + 1]],p[idm[i]]))
        {
            ++r;
            add(s1[idn[r]]);
        }
        while (r >= l && !check(s[idn[r]],p[idm[i]]))
        {
            del(s1[idn[r]]);
            --r;
        }
        res[idm[i]] = calc(q[idm[i]]);
    }
    for (int i = 1;i <= m;++i) cout << res[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("D.inp","r",stdin);
//    freopen("D.out","w",stdout);
    input();
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'bool check(const string&, const string&)':
selling_rna.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0;i < a.size();++i)
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int tk(char)':
selling_rna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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