oj.uz

Submission #1070504

# Submission time Handle Problem Language Result Execution time Memory
1070504 2024-08-22T14:48:13 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 89 ms 117844 KB 
#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();
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16728 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 58704 KB Output is correct
2 Correct 42 ms 61012 KB Output is correct
3 Correct 47 ms 28500 KB Output is correct
4 Correct 55 ms 27656 KB Output is correct
5 Runtime error 89 ms 117844 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17244 KB Output is correct
2 Correct 16 ms 16988 KB Output is correct
3 Correct 20 ms 16984 KB Output is correct
4 Correct 16 ms 17136 KB Output is correct
5 Correct 25 ms 16984 KB Output is correct
6 Correct 24 ms 17028 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16728 KB Output is correct
8 Correct 37 ms 58704 KB Output is correct
9 Correct 42 ms 61012 KB Output is correct
10 Correct 47 ms 28500 KB Output is correct
11 Correct 55 ms 27656 KB Output is correct
12 Runtime error 89 ms 117844 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -