oj.uz

Submission #1070537

# Submission time Handle Problem Language Result Execution time Memory
1070537 2024-08-22T15:06:17 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1394 ms 490208 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 t)
{
    long long n=t.size(), i;
    string t1="";
    for (i=0; i<n; i++)
    {
        if (t[i]=='C') {t1+='a';}
        else if (t[i]=='U') {t1+='b';}
        else if (t[i]=='G') {t1+='c';}
        else {t1+='d';};
    };
    return t1;
}

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

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

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

vector<long long> solvesuf(string t)
{
    long long n=t.size(), i, j=0;
    vector<long long> v;
    for (i=0; i<n-1; i++)
    {
        if (b[j][t[i]-'a']==0) {return v;};
        j=b[j][t[i]-'a'];
    };
    return ans[j][t[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 78 ms 238236 KB Output is correct
2 Correct 80 ms 238456 KB Output is correct
3 Correct 86 ms 238288 KB Output is correct
4 Correct 83 ms 238416 KB Output is correct
5 Correct 96 ms 238364 KB Output is correct
6 Correct 82 ms 238308 KB Output is correct
7 Correct 77 ms 238288 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 380752 KB Output is correct
2 Correct 256 ms 373332 KB Output is correct
3 Correct 226 ms 490208 KB Output is correct
4 Correct 215 ms 478800 KB Output is correct
5 Correct 255 ms 468868 KB Output is correct
6 Correct 253 ms 472404 KB Output is correct
7 Correct 132 ms 256848 KB Output is correct
8 Correct 248 ms 387432 KB Output is correct
9 Correct 232 ms 365096 KB Output is correct
10 Correct 201 ms 362832 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 240640 KB Output is correct
2 Correct 176 ms 240172 KB Output is correct
3 Correct 192 ms 240064 KB Output is correct
4 Correct 165 ms 239564 KB Output is correct
5 Correct 252 ms 240440 KB Output is correct
6 Correct 376 ms 240392 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 238236 KB Output is correct
2 Correct 80 ms 238456 KB Output is correct
3 Correct 86 ms 238288 KB Output is correct
4 Correct 83 ms 238416 KB Output is correct
5 Correct 96 ms 238364 KB Output is correct
6 Correct 82 ms 238308 KB Output is correct
7 Correct 77 ms 238288 KB Output is correct
8 Correct 227 ms 380752 KB Output is correct
9 Correct 256 ms 373332 KB Output is correct
10 Correct 226 ms 490208 KB Output is correct
11 Correct 215 ms 478800 KB Output is correct
12 Correct 255 ms 468868 KB Output is correct
13 Correct 253 ms 472404 KB Output is correct
14 Correct 132 ms 256848 KB Output is correct
15 Correct 248 ms 387432 KB Output is correct
16 Correct 232 ms 365096 KB Output is correct
17 Correct 201 ms 362832 KB Output is correct
18 Correct 880 ms 240640 KB Output is correct
19 Correct 176 ms 240172 KB Output is correct
20 Correct 192 ms 240064 KB Output is correct
21 Correct 165 ms 239564 KB Output is correct
22 Correct 252 ms 240440 KB Output is correct
23 Correct 376 ms 240392 KB Output is correct
24 Correct 236 ms 356948 KB Output is correct
25 Correct 278 ms 356944 KB Output is correct
26 Correct 270 ms 355668 KB Output is correct
27 Correct 280 ms 447180 KB Output is correct
28 Correct 1394 ms 276248 KB Output is correct
29 Correct 200 ms 247984 KB Output is correct