Submission #1091355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091355		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	45 ms	54732 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=(j);i>=(k);i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+6;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=123456789;

int n,m;

int node[maxn][4],Time;
vector<int> L[maxn];
string s[maxn];
void Transform(string& s)
{
    for(char& c:s)
    {
        if (c=='U') c='B';
        else if (c=='G') c='D';
    }
}
void sol()
{
    cin >> n>> m;
    for1(i,1,n)
    {
        cin >> s[i];
        Transform(s[i]);
    }
    memset(node,-1,sizeof(node));
    sort(s+1,s+1+n);
    for1(i,1,n)
    {
        int cur=0;
        string x=s[i];
        reverse(all(x));
        for(char c:x)
        {
            if (node[cur][c-'A']==-1) node[cur][c-'A']=++Time;
            cur=node[cur][c-'A'];
            L[cur].pb(i);
        }
    }
    for1(i,1,m)
    {
        string p,q;
        cin>>p>>q;
        Transform(p);
        Transform(q);
        int l=lower_bound(s+1,s+1+n,p)-s;
        p.back()++;
        int r=lower_bound(s+1,s+1+n,p)-s-1;
        if (r<l)
        {
            cout << "0\n";
            continue;
        }
        reverse(all(q));
        int cur=0;
        for(char c:q)
        {
            cur=node[cur][c-'A'];
            if (cur==-1) break;
        }
        if (cur==-1)
        {
            cout << "0\n";
            continue;
        }
        cout << upper_bound(all(L[cur]),r)-lower_bound(all(L[cur]),l)<<'\n';
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("PAINT.inp","r",stdin);
//    freopen("PAINT.out","w",stdout);
    int t=1;//cin>>t;
    while (t--)
    {
        sol();
    }
}
/*
*/

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