제출 #1170386

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

selling_rna

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
string 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<string,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());
        sufix[i]=suf;
    }
    sort(events+1,events+total_ev+1);
}

void solve(){
    int i;
    for(i=1;i<=total_ev;++i)
        if(events[i].type==0){
            string suf;
            int id;
            for(id=(int)events[i].sir.size()-1;id>=0;--id){
                suf.push_back(events[i].sir[id]);
                ++mep[suf];
            }
        }
        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