Submission #1220234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220234		mariamtsagareli	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	3 ms	2372 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
struct T{array<int,4>n;int tin,tout;T(){n.fill(0);}};
int cv(char c){return c=='A'?0:c=='G'?1:c=='C'?2:3;}
void df(vector<T>&t,int u,int&c){t[u].tin=++c;for(int d=0;d<4;d++)if(t[u].n[d])df(t,t[u].n[d],c);t[u].tout=c;}
struct F{int x,l,r,s,i;};
struct B{int n;vector<int>t;B(int n):n(n),t(n+1){};void u(int i,int v){for(;i<=n;i+=i&-i)t[i]+=v;}int q(int i){int s=0;for(;i>0;i-=i&-i)s+=t[i];return s;}};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k,c,g;
    cin>>n>>k>>c>>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];
    vector<T>tp(1),tq(1);
    for(int i=0;i<n;i++){
        int u=0;
        for(char ch:s[i]){
            int d=cv(ch);
            if(!tp[u].n[d]){tp[u].n[d]=tp.size();tp.emplace_back();}
            u=tp[u].n[d];
        }
    }
    for(int i=0;i<n;i++){
        int u=0;
        for(int j=s[i].size()-1;j>=0;j--){
            int d=cv(s[i][j]);
            if(!tq[u].n[d]){tq[u].n[d]=tq.size();tq.emplace_back();}
            u=tq[u].n[d];
        }
    }
    int cp=0,cs=0;
    df(tp,0,cp);
    df(tq,0,cs);
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;i++){
        int u=0;
        for(char ch:s[i])u=tp[u].n[cv(ch)];
        int x=tp[u].tin;
        u=0;
        for(int j=s[i].size()-1;j>=0;j--)u=tq[u].n[cv(s[i][j])];
        int y=tq[u].tin;
        v[i]={x,y};
    }
    vector<F>e;
    for(int i=0;i<m;i++){
        int u=0,l1,r1,l2,r2;
        for(char ch:p[i]){
            int d=cv(ch);
            if(!tp[u].n[d]){u=-1;break;}
            u=tp[u].n[d];
        }
        if(u<0)continue;
        l1=tp[u].tin;r1=tp[u].tout;
        u=0;
        for(int j=q[i].size()-1;j>=0;j--){
            int d=cv(q[i][j]);
            if(!tq[u].n[d]){u=-1;break;}
            u=tq[u].n[d];
        }
        if(u<0)continue;
        l2=tq[u].tin;r2=tq[u].tout;
        e.push_back({r1,l2,r2,1,i});
        e.push_back({l1-1,l2,r2,-1,i});
    }
    sort(v.begin(),v.end());
    sort(e.begin(),e.end(),[](auto&a,auto&b){return a.x<b.x;});
    B b(cs);
    vector<long long>ans(m);
    int j=0;
    for(auto&f:e){
        while(j<n&&v[j].first<=f.x){
            b.u(v[j].second,1);
            j++;
        }
        int t=b.q(f.r)-b.q(f.l-1);
        ans[f.i]+=f.s*(long long)t;
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
    return 0;
}

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