Submission #856976

#	Time	Username	Problem	Language	Result	Execution time	Memory
856976		TS_2392	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	105 ms	112128 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 100005
using namespace std;
int n,m;
string S[N];
struct iii {
    string p,q;
    int id;
} T[N];
int cnt=0;
int Trie[2000005][4],Min[2000005],Max[2000005],End[2000005];
void Add(string s,int id) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) Trie[u][x]=++cnt;
        u=Trie[u][x];
        if (!Min[u]) Min[u]=id;
        Max[u]=id;
    }
}
ii Get(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) return {0,0};
        u=Trie[u][x];
    }
    return {Min[u],Max[u]};
}
vector < int > adj[N];
int ans[N];
void Add2(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) Trie[u][x]=++cnt;
        u=Trie[u][x];
        ++End[u];
    }
}
int Get2(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) return 0;
        u=Trie[u][x];
    }
    return End[u];
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    FOR(i,1,n) cin>>S[i];
    sort(S+1,S+n+1);
    FOR(i,1,n) Add(S[i],i);
    //FOR(i,1,n) cout<<S[i]<<'\n';
    FOR(i,1,m) {
        cin>>T[i].p>>T[i].q;
        reverse(T[i].q.begin(),T[i].q.end());
        ii tmp=Get(T[i].p);
        int l=tmp.f,r=tmp.s;
        if (l && r && l<=r) {
            adj[l-1].pb(-i);
            adj[r].pb(i);
        }
        //cout<<l<<" "<<r<<'\n';
    }
    memset(Trie,0,sizeof(Trie));
    cnt=0;
    FOR(i,1,n) {
        reverse(S[i].begin(),S[i].end());
        Add2(S[i]);
        //cout<<S[i]<<'\n';
        for (auto j : adj[i]) {
            int id=abs(j);
            int val=Get2(T[id].q);
            if (j<0) ans[id]-=val;
            else ans[id]+=val;
            //if (id==2) cout<<i<<" "<<T[id].q<<" "<<val<<'\n';
        }
    }
    FOR(i,1,m) cout<<ans[i]<<'\n';
    return 0;
}

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