Submission #1225826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225826		mariamtsagareli	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	273 ms	237744 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct B{int n;vi t;B(int n):n(n),t(n+1){};void u(int i){for(;i<=n;i+=i&-i)t[i]++;}int q(int i){int s=0;for(;i>0;i-=i&-i)s+=t[i];return s;}int qr(int l,int r){return q(r)-q(l-1);}};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;cin>>n>>m;
    vector<string>s(n);
    for(int i=0;i<n;i++)cin>>s[i];
    vector<string>p(m),q(m);
    for(int i=0;i<m;i++)cin>>p[i]>>q[i];
    int c1=1;
    vector<array<int,4>>ch1(2000005);
    vi tin1(2000005),tout1(2000005);
    for(int i=0;i<2000005;i++)for(int j=0;j<4;j++)ch1[i][j]=0;
    for(auto&x:s){
        int u=1;
        for(char cc:x){
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            if(!ch1[u][v])ch1[u][v]=++c1;
            u=ch1[u][v];
        }
    }
    int t1=0;
    vector<vector<int>>e1(c1+1);
    for(int u=1;u<=c1;u++)for(int v=0;v<4;v++)if(ch1[u][v])e1[u].push_back(ch1[u][v]);
    function<void(int)>d1=[&](int u){
        tin1[u]=++t1;
        for(int v:e1[u])d1(v);
        tout1[u]=t1;
    };
    d1(1);

    int c2=1;
    vector<array<int,4>>ch2(2000005);
    vi tin2(2000005),tout2(2000005);
    for(int i=0;i<2000005;i++)for(int j=0;j<4;j++)ch2[i][j]=0;
    for(auto&x:s){
        int u=1;
        for(int i=x.size()-1;i>=0;i--){
            char cc=x[i];
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            if(!ch2[u][v])ch2[u][v]=++c2;
            u=ch2[u][v];
        }
    }
    int t2=0;
    vector<vector<int>>e2(c2+1);
    for(int u=1;u<=c2;u++)for(int v=0;v<4;v++)if(ch2[u][v])e2[u].push_back(ch2[u][v]);
    function<void(int)>d2=[&](int u){
        tin2[u]=++t2;
        for(int v:e2[u])d2(v);
        tout2[u]=t2;
    };
    d2(1);

    vector<pair<int,int>>pts(n);
    for(int i=0;i<n;i++){
        int u=1;
        for(char cc:s[i]){
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            u=ch1[u][v];
        }
        int x=tin1[u];
        u=1;
        for(int i2=s[i].size()-1;i2>=0;i2--){
            char cc=s[i][i2];
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            u=ch2[u][v];
        }
        int y=tin2[u];
        pts[i]={x,y};
    }
    struct Q{int x,l,r,i,sg;};
    vector<Q>qs;
    for(int i=0;i<m;i++){
        int u=1;
        bool ok=true;
        for(char cc:p[i]){
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            if(!ch1[u][v]){ok=false;break;}
            u=ch1[u][v];
        }
        int l1,r1;
        if(!ok)l1=1,r1=0;
        else l1=tin1[u],r1=tout1[u];
        u=1;ok=true;
        for(int j2=q[i].size()-1;j2>=0;j2--){
            char cc=q[i][j2];
            int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
            if(!ch2[u][v]){ok=false;break;}
            u=ch2[u][v];
        }
        int l2,r2;
        if(!ok)l2=1,r2=0;
        else l2=tin2[u],r2=tout2[u];
        if(l1>r1||l2>r2)continue;
        qs.push_back({r1,l2,r2,i,1});
        qs.push_back({l1-1,l2,r2,i,-1});
    }
    sort(pts.begin(),pts.end());
    sort(qs.begin(),qs.end(),[](auto &a,auto &b){return a.x<b.x;});
    B bit(t2);
    vi ans(m);
    int pi=0;
    for(auto &qv:qs){
        while(pi<n&&pts[pi].first<=qv.x){
            bit.u(pts[pi].second);
            pi++;
        }
        ans[qv.i]+=qv.sg*bit.qr(qv.l,qv.r);
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
    return 0;
}

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