제출 #1318996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318996		wangzhiyi33	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	490 ms	658408 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;
vector<int>kos;

struct trie{
    trie *ch[26];
    int mn,mx;
    vector<int>isi;

    trie(){
        for(int q=0;q<26;q++){
            ch[q]=0;
        }
        mn=1e18,mx=0;
    }

    void add(int idx,string &s,int apa){
        if(idx==s.length()){
            mx=apa,mn=min(mn,apa);
            return;
        }
        int nxt=s[idx]-'A';
        if(!ch[nxt]){
            ch[nxt]=new trie();
        }
        ch[nxt]->add(idx+1,s,apa);
        mx=apa,mn=min(mn,apa);
    }

    void rev(int idx,string &s,int apa){
        if(idx==s.length()){
            isi.pb(apa);
            return;
        }
        int nxt=s[s.length()-idx-1]-'A';
        if(!ch[nxt]){
            ch[nxt]=new trie();
        }
        ch[nxt]->rev(idx+1,s,apa);
        isi.pb(apa);
    }

    ii mnx(int idx,string &s){
        if(idx==s.length())return {mn,mx};
        int apa=s[idx]-'A';
        if(!ch[apa]){
            return {1e18,0};
        }
        return ch[apa]->mnx(idx+1,s);
    }

    vector<int> &src(int idx,string &s){
        if(idx==s.length())return isi;
        int apa=s[idx]-'A';
        if(!ch[apa]){
            return kos;
        }
        return ch[apa]->src(idx+1,s);
    }

};

signed main(){
    int n,qu;
    cin>>n>>qu;
    string s[n+1];
    for(int q=1;q<=n;q++){
        cin>>s[q];
    }
    sort(s+1,s+n+1);

    trie cur;
    for(int q=1;q<=n;q++){
        cur.add(0,s[q],q);
        cur.rev(0,s[q],q);
    }

    while(qu--){
        string a,b;
        cin>>a>>b;

        ii apa=cur.mnx(0,a);
        reverse(b.begin(),b.end());
        vector<int>&has=cur.src(0,b);
        
        if(apa.fir==1e18 || apa.sec==0 || has.empty()){
            cout<<0<<endl;
        }
        else{
            int mul=lower_bound(has.begin(),has.end(),apa.fir)-has.begin();
            int akh=upper_bound(has.begin(),has.end(),apa.sec)-has.begin();
            cout<<akh-mul<<endl;
        }
    }
}

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