oj.uz

Submission #1069523

# Submission time Handle Problem Language Result Execution time Memory
1069523 2024-08-22T04:57:36 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 16 ms 28248 KB 
#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);
        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.l/BLOCK!=y.l/BLOCK)
        {
            return x.l/BLOCK<y.l/BLOCK;
        }
        return x.r<y.r;
    });
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 28248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 22104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -