Submission #1258877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258877		hamanp87	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	147 ms	72024 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<string,string> pss;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int inf=1e9,mod=1e9+7,neginf=-1e9;
const double PI=acos(-1);

struct Trie
{
    vector<array<int,4>> nxt;
    Trie()
    {
        nxt.pub({-1,-1,-1,-1});
    }

    int ind(char c)
    {
        if(c=='A')
            return 0;
        if(c=='C')
            return 1;
        if(c=='G')
            return 2;
        return 3;
    }

    int Add()
    {
        nxt.pub({-1,-1,-1,-1});
        return (int)nxt.size()-1;
    }

    int insert(const string &s)
    {
        int v=0;
        for(char c:s)
        {
            int i=ind(c);
            if(nxt[v][i]==-1)
                nxt[v][i]=Add();
            v=nxt[v][i];
        }
        return v;
    }

    int check(const string &s)
    {
        int v=0;
        for(char c:s)
        {
            int i=ind(c);
            if(nxt[v][i]==-1)
                return -1;
            v=nxt[v][i];
        }
        return v;
    }

    int size() const
    {
        return (int)nxt.size();
    }
};

void bfs(const Trie &T,veci &tin,veci &tout)
{
    int n=T.size();
    tin.assign(n,0);
    tout.assign(n,0);
    int tim=0;
    vecp st;
    st.reserve(n);
    st.emplace_back(0,0);
    while(st.size())
    {
        auto &pr=st.back();
        int u=pr.F;
        int &ch=pr.S;
        if(ch==0)
            tin[u]=++tim;
        if(ch<4)
        {
            int v=T.nxt[u][ch];
            ch++;
            if(v!=-1)
            {
                st.emplace_back(v,0);
            }
        }
        else
        {
            tout[u]=tim;
            st.pob();
        }
    }
}

struct Fenwick
{
    int n;
    veci f;
    Fenwick(int m)
    {
        n=m;
        f.assign(n+1,0);
    }

    void update(int i,int v)
    {
        for(;i<=n;i+=i&-i)
            f[i]+=v;
    }

    int sum(int i)
    {
        int s=0;
        for(;i>0;i-=i&-i)
            s+=f[i];

        return s;
    }

    int get(int l,int r)
    {
        if(r<l)
            return 0;
        return sum(r)-sum(l-1);
    }
};

struct Point
{
    int x,y;
};

struct Event
{
    int x,ly,ry,id,c;
};

bool cmpp(Point &a,Point &b)
{
    return a.x<b.x;
}

bool cmpe(Event &a,Event &b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.c<b.c;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<string> ss(n);
    for(int i=0;i<n;i++)
        cin>>ss[i];
    vector<pss> Qs(m);
    for(int i=0;i<m;i++)
        cin>>Qs[i].F>>Qs[i].S;

    Trie Prf;
    veci prt(n);
    for(int i=0;i<n;i++)
        prt[i]=Prf.insert(ss[i]);

    Trie Suf;
    veci sft(n);
    for(int i=0;i<n;i++)
    {
        string s=ss[i];
        reverse(all(s));
        sft[i]=Suf.insert(s);
    }

    veci tinp,toutp;
    bfs(Prf,tinp,toutp);
    veci tins,touts;
    bfs(Suf,tins,touts);

    vector<Point> pts;
    pts.reserve(n);
    for(int i=0;i<n;i++)
        pts.pub({tinp[prt[i]],tins[sft[i]]});
    sort(all(pts),cmpp);

    vector<Event> evs;
    evs.reserve(2*m);
    vecl ans(m,0);

    for(int i=0;i<m;i++)
    {
        const string &p=Qs[i].F;
        const string &q=Qs[i].S;
        int np=Prf.check(p);
        if(np==-1)
        {
            ans[i]=0;
            continue;
        }

        string rq=q;
        reverse(all(rq));
        int nq=Suf.check(rq);
        if(nq==-1)
        {
            ans[i]=0;
            continue;
        }

        int lx=tinp[np],rx=toutp[np];
        int ly=tins[nq],ry=touts[nq];

        evs.pub({rx-0,ly,ry,i,+1});
        evs.pub({lx-1,ly,ry,i,-1});
    }

    sort(all(evs),cmpe);

    int may=(int)Suf.size()+10;
    Fenwick Fen(may);
    int pind=0;
    for(auto &ev:evs)
    {
        while(pind<(int)pts.size() and pts[pind].x<=ev.x)
        {
            Fen.update(pts[pind].y,1);
            pind++;
        }
        ll cnt=Fen.get(ev.ly,ev.ry);
        ans[ev.id]+=ev.c*cnt;
    }

    for(int i=0;i<m;i++)
        cout<<ans[i]<<"\n";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    //ifstream fin("in.txt");
    //ofstream fout("out.txt");

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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