oj.uz

Submission #1070533

# Submission time Handle Problem Language Result Execution time Memory
1070533 2024-08-22T15:02:59 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1302 ms 490064 KB 
#include <bits/stdc++.h>
using namespace std;

long long a[2000005][5], b[2000005][5], l[2000005][5], r[2000005][5], id1=1, id2=1;
vector<long long> ans[2000005][5];
string s[100005], pre, suf;

string fix(string s)
{
    long long n=s.size(), i;
    string t="";
    for (i=0; i<n; i++)
    {
        if (s[i]=='C') {t+='a';}
        else if (s[i]=='U') {t+='b';}
        else if (s[i]=='G') {t+='c';}
        else {t+='d';};
    };
    return t;
}

void add(string s, long long k)
{
    long long n=s.size(), i, j=0;
    for (i=0; i<n; i++)
    {
        if (a[j][s[i]-'a']==0) {a[j][s[i]-'a']=id1++; l[j][s[i]-'a']=r[j][s[i]-'a']=k;}
        else {r[j][s[i]-'a']=k;};
        j=a[j][s[i]-'a'];
    };
}

void addsuf(string s, long long k)
{
    long long n=s.size(), i, j=0;
    for (i=0; i<n; i++)
    {
        if (b[j][s[i]-'a']==0) {b[j][s[i]-'a']=id2++;};
        ans[j][s[i]-'a'].push_back(k);
        j=b[j][s[i]-'a'];
    };
}

pair<long long, long long> solvepre(string s)
{
    long long n=s.size(), i, j=0;
    for (i=0; i<n-1; i++)
    {
        if (a[j][s[i]-'a']==0) {return {0LL, 0LL};};
        j=a[j][s[i]-'a'];
    };
    return {l[j][s[n-1]-'a'], r[j][s[n-1]-'a']};
}

vector<long long> solvesuf(string s)
{
    long long n=s.size(), i, j=0;
    vector<long long> v;
    for (i=0; i<n-1; i++)
    {
        if (b[j][s[i]-'a']==0) {return v;};
        j=b[j][s[i]-'a'];
    };
    return ans[j][s[n-1]-'a'];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m, i;
    pair<long long, long long> p;
    vector<long long> v;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        cin >> s[i];
        s[i]=fix(s[i]);
    };
    sort(s+1, s+n+1);
    for (i=1; i<=n; i++)
    {
        add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        addsuf(s[i], i);
    };
    while (m--)
    {
        cin >> pre >> suf;
        pre=fix(pre); suf=fix(suf);
        p=solvepre(pre);
        reverse(suf.begin(), suf.end());
        v=solvesuf(suf);
        cout << upper_bound(v.begin(), v.end(), p.second)-lower_bound(v.begin(), v.end(), p.first) << "\n";
    };
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 238304 KB Output is correct
2 Correct 87 ms 238284 KB Output is correct
3 Correct 80 ms 238416 KB Output is correct
4 Correct 82 ms 238420 KB Output is correct
5 Correct 79 ms 238328 KB Output is correct
6 Correct 83 ms 238420 KB Output is correct
7 Correct 89 ms 238416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 380748 KB Output is correct
2 Correct 244 ms 373328 KB Output is correct
3 Correct 251 ms 490064 KB Output is correct
4 Correct 222 ms 478544 KB Output is correct
5 Correct 246 ms 468816 KB Output is correct
6 Correct 253 ms 472400 KB Output is correct
7 Correct 134 ms 256632 KB Output is correct
8 Correct 255 ms 387408 KB Output is correct
9 Correct 245 ms 365136 KB Output is correct
10 Correct 215 ms 362804 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 240680 KB Output is correct
2 Correct 175 ms 240172 KB Output is correct
3 Correct 201 ms 240076 KB Output is correct
4 Correct 162 ms 239656 KB Output is correct
5 Correct 257 ms 240448 KB Output is correct
6 Correct 394 ms 240420 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 238304 KB Output is correct
2 Correct 87 ms 238284 KB Output is correct
3 Correct 80 ms 238416 KB Output is correct
4 Correct 82 ms 238420 KB Output is correct
5 Correct 79 ms 238328 KB Output is correct
6 Correct 83 ms 238420 KB Output is correct
7 Correct 89 ms 238416 KB Output is correct
8 Correct 248 ms 380748 KB Output is correct
9 Correct 244 ms 373328 KB Output is correct
10 Correct 251 ms 490064 KB Output is correct
11 Correct 222 ms 478544 KB Output is correct
12 Correct 246 ms 468816 KB Output is correct
13 Correct 253 ms 472400 KB Output is correct
14 Correct 134 ms 256632 KB Output is correct
15 Correct 255 ms 387408 KB Output is correct
16 Correct 245 ms 365136 KB Output is correct
17 Correct 215 ms 362804 KB Output is correct
18 Correct 880 ms 240680 KB Output is correct
19 Correct 175 ms 240172 KB Output is correct
20 Correct 201 ms 240076 KB Output is correct
21 Correct 162 ms 239656 KB Output is correct
22 Correct 257 ms 240448 KB Output is correct
23 Correct 394 ms 240420 KB Output is correct
24 Correct 244 ms 356944 KB Output is correct
25 Correct 283 ms 356948 KB Output is correct
26 Correct 253 ms 355672 KB Output is correct
27 Correct 275 ms 447180 KB Output is correct
28 Correct 1302 ms 276244 KB Output is correct
29 Correct 207 ms 247984 KB Output is correct