제출 #1091654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091654		DucNguyen2007	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	502 ms	595536 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5,BLOCK=320;
const ll inf=2e18;
int n,m,ans[maxN+1];
struct query
{
    int l,r,id;
}p[maxN+1];
string a[maxN+1],q[maxN+1],b[maxN+1];
struct Trie
{
    struct Node
    {
        Node *child[26];
        int cnt,l,r;
        Node()
        {
            for(int i=0;i<26;i++)
            {
                child[i]=NULL;
            }
            cnt=l=r=0;
        }
    };
    Node root;
    void add(string s,int id)
    {
        Node *cur=&root;
        for(auto c:s)
        {
            int d=(c-'A');
            if(!(cur->child[d]))
            {
                cur->child[d]=new Node();
            }
            cur=cur->child[d];
            if(!cur->l)
            {
                cur->l=id;
            }
            cur->r=id;
            cur->cnt++;
        }
    }
    void del(string s)
    {
        Node *cur=&root;
        for(auto c:s)
        {
            int d=(c-'A');
            cur=cur->child[d];
            cur->cnt--;
        }
    }
    pii walk(string s)
    {
        Node *cur=&root;
        for(auto c:s)
        {
            int d=(c-'A');
            if(!(cur->child[d]))
            {
                return {-1,-1};
            }
            cur=cur->child[d];
        }
        return {cur->l,cur->r};
    }
    int Walk(string s)
    {
        Node *cur=&root;
        for(auto c:s)
        {
            int d=(c-'A');
            if(!(cur->child[d]))
            {
                return 0;
            }
            cur=cur->child[d];
        }
        return cur->cnt;
    }
}f,f1;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        f.add(a[i],i);
        //cout<<a[i]<<'\n';
        b[i]=a[i];
        reverse(b[i].begin(),b[i].end());
    }
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        string d;
        cin>>d>>q[i];
        reverse(q[i].begin(),q[i].end());
        pii tmp=f.walk(d);
        p[i].l=tmp.fi;
        p[i].r=tmp.se;
        p[i].id=i;
    }
    sort(p+1,p+m+1,[&](query x,query y)
    {
        if(x.r/BLOCK==y.r/BLOCK)
        {
            return x.l<y.l;
        }
        return x.r/BLOCK<y.r/BLOCK;
    });
    int lo=1,hi=0;
    for(int i=1;i<=m;i++)
    {
        int l=p[i].l,r=p[i].r;
        if(l==-1&&r==-1)
        {
            continue;
        }
        //cout<<l<<" "<<r<<'\n';
        while(hi<r)
        {
            hi++;
            f1.add(b[hi],i);
            //cout<<b[hi]<<'\n';
        }
        while(lo>l)
        {
            lo--;
            f1.add(b[lo],i);
        }
        while(hi>r)
        {
            f1.del(b[hi]);
            hi--;
        }
        while(lo<l)
        {
            f1.del(b[lo]);
            lo++;
        }
        //cout<<q[p[i].id]<<'\n';
        ans[p[i].id]=f1.Walk(q[p[i].id]);
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<'\n';
    }
}

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