Submission #729971

#	Time	Username	Problem	Language	Result	Execution time	Memory
729971		n0sk1ll	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	217 ms	155992 KiB

selling_rna

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const int N=6'000'006;

struct pers_segtree
{
    int val[N],L[N],R[N];
    int idx=0;

    int root[200005];

    //root se podrazumeva da je kec (1)

    void add(int p, int q, int l, int r, int s, int x)
    {
        val[p]=val[q]+x;
        if (l==r) return;
        int mid=(l+r)/2;
        if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
        else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
    }

    int sum(int p, int q, int l, int r, int ll, int rr)
    {
        if (ll>r || rr<l) return 0;
        if (ll<=l && rr>=r) return val[p]-val[q];
        int mid=(l+r)/2;
        return sum(L[p],L[q],l,mid,ll,rr)+sum(R[p],R[q],mid+1,r,ll,rr);
    }
} ST;

struct nicetrie
{
    int idx=1;
    int node[2000006][4];
    vector<int> inds[2000006];
    int tin[2000006],tout[2000006];
    int perm[2000006];

    //root se podrazumeva da je kec (1)

    void add(string &s, int ind)
    {
        int p=1;

        for (auto c : s)
        {
            int gde;
            if (c=='A') gde=0;
            else if (c=='C') gde=1;
            else if (c=='G') gde=2;
            else gde=3;

            if (!node[p][gde]) node[p][gde]=++idx;
            p=node[p][gde];
        }

        inds[p].pb(ind);
    }

    int VREME=1;
    void dfs(int p)
    {
        tin[p]=VREME;
        for (auto it : inds[p]) perm[VREME++]=it;
        ff(i,0,4) if (node[p][i]) dfs(node[p][i]);
        tout[p]=VREME;
    }

    pii le_find(string &s)
    {
        int p=1;

        for (auto c : s)
        {
            int gde;
            if (c=='A') gde=0;
            else if (c=='C') gde=1;
            else if (c=='G') gde=2;
            else gde=3;

            p=node[p][gde];
            if (!p) return {-1,-1};
        }

        return {tin[p],tout[p]-1};
    }
} pref, suf;

int gdeusuf[200005];
int sami[200005];

int main()
{
    FAST;

    int n,q; cin>>n>>q;
    fff(i,1,n)
    {
        string s; cin>>s;
        pref.add(s,i);

        reverse(all(s));
        suf.add(s,i);
    }

    pref.dfs(1);
    suf.dfs(1);

    fff(i,1,n) gdeusuf[suf.perm[i]]=i;
    fff(i,1,n) sami[i]=gdeusuf[pref.perm[i]];

    ST.root[0]=++ST.idx;
    fff(i,1,n)
    {
        ST.root[i]=++ST.idx;
        ST.add(ST.root[i],ST.root[i-1],1,n,sami[i],1);
    }

    while (q--)
    {
        string a,b; cin>>a>>b; reverse(all(b));
        auto [l1,r1]=pref.le_find(a);
        auto [l2,r2]=suf.le_find(b);

        //cout<<"["<<l1<<","<<r1<<"] x ["<<l2<<","<<r2<<"]: ";
        if (l1>r1 || l2>r2 || l1==-1 || l2==-1 || r1==-1 || r2==-1) cout<<0<<"\n";
        else cout<<ST.sum(ST.root[r1],ST.root[l1-1],1,n,l2,r2)<<"\n";
    }
}

//Note to self: Check for overflow

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