제출 #1170398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170398		AlgorithmWarrior	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1598 ms	106200 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int const BASE=31;
int const MOD=1e9+7;
int const MAX=2e5+5;
int sufix[MAX];
int ans[MAX];
int n,m;
int total_ev;
struct event{
    string sir;
    int id,type;
    bool operator<(event ot){
        if(sir==ot.sir)
            return type>ot.type;
        return sir<ot.sir;
    }
}events[MAX];
map<int,int>mep;

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i){
        string s;
        cin>>s;
        events[++total_ev]={s,0,0};
    }
    for(i=1;i<=m;++i){
        string pref,suf;
        cin>>pref>>suf;
        events[++total_ev]={pref,i,1};
        pref.push_back('Z');
        events[++total_ev]={pref,i,2};
        reverse(suf.begin(),suf.end());
        int bpow=1;
        int id;
        int nr=0;
        for(id=0;id<(int)suf.size();++id){
            nr=(nr+1LL*bpow*(suf[id]-'A'+1)%MOD)%MOD;
            bpow=1LL*bpow*BASE%MOD;
        }
        sufix[i]=nr;
    }
    sort(events+1,events+total_ev+1);
}

void solve(){
    int i;
    for(i=1;i<=total_ev;++i)
        if(events[i].type==0){
            int nr=0;
            int id;
            int bpow=1;
            for(id=(int)events[i].sir.size()-1;id>=0;--id){
                nr=(nr+1LL*bpow*(events[i].sir[id]-'A'+1)%MOD)%MOD;
                ++mep[nr];
                bpow=1LL*bpow*BASE%MOD;
            }
        }
        else
            if(events[i].type==1)
                ans[events[i].id]-=mep[sufix[events[i].id]];
            else
                ans[events[i].id]+=mep[sufix[events[i].id]];
}

void write(){
    int i;
    for(i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
}

int main()
{
    read();
    solve();
    write();
    return 0;
}

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