Submission #1079060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079060		alexander707070	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	211 ms	336984 KiB

selling_rna

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

struct event{
    int l,r,id;
};

struct node{
    vector<int> words;
    int ch[4];
};

int n,m;
string word[MAXN],s,t;

node prefix[2000007],suffix[2000007];
int pr,sf;

void transform(string &s){
    for(int f=0;f<s.size();f++){
        if(s[f]=='G')s[f]='B';
        if(s[f]=='U')s[f]='D';
    }
}

void add(string s,int id){
    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0){
            pr++; prefix[curr].ch[s[i]-'A']=pr;
        }

        curr=prefix[curr].ch[s[i]-'A'];
    }

    prefix[curr].words.push_back(id);

    reverse(s.begin(),s.end());

    curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0){
            sf++; suffix[curr].ch[s[i]-'A']=sf;
        }

        curr=suffix[curr].ch[s[i]-'A'];
    }

    suffix[curr].words.push_back(id);
}

int num,in[MAXN],ans[MAXN];
int euler[MAXN],pos;

int mins[MAXN],maxs[MAXN];
int from[MAXN],to[MAXN];

void dfs(int x){
    mins[x]=num+1;

    for(int i:prefix[x].words){
        num++; in[i]=num;
    }

    for(int i=0;i<4;i++){
        if(prefix[x].ch[i]!=0)dfs(prefix[x].ch[i]);
    }

    maxs[x]=num;
}

void dfs2(int x){
    from[x]=pos+1;

    for(int i:suffix[x].words){
        pos++; euler[pos]=in[i];
    }

    for(int i=0;i<4;i++){
        if(suffix[x].ch[i]!=0)dfs2(suffix[x].ch[i]);
    }

    to[x]=pos;
}


int findpref(string s){
    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0)return -1;
        curr=prefix[curr].ch[s[i]-'A'];
    }
    
    return curr;
}

int findsuff(string s){
    reverse(s.begin(),s.end());

    int curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0)return -1;
        curr=suffix[curr].ch[s[i]-'A'];
    }

    return curr;
}

vector<event> query[MAXN];

int fenwick[MAXN];

void update(int x){
    while(x<=n){
        fenwick[x]++;
        x+=(x & (-x));
    }
}

int getsum(int x){
    int res=0;

    while(x>=1){
        res+=fenwick[x];
        x-=(x & (-x));
    }

    return res;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>word[i];

        transform(word[i]);

        add(word[i],i);
    }

    dfs(0);
    dfs2(0);

    for(int i=1;i<=m;i++){
        cin>>s>>t;

        transform(s);
        transform(t);

        int a=findpref(s);
        int b=findsuff(t);

        if(a==-1 or b==-1)continue;
        if(mins[a]>maxs[a] or from[b]>to[b])continue;

        query[from[b]-1].push_back({mins[a],maxs[a],-i});
        query[to[b]].push_back({mins[a],maxs[a],i});
    }

    for(int i=1;i<=pos;i++){
        update(euler[i]);

        for(event e:query[i]){
            if(e.id<0){
                ans[-e.id]-=getsum(e.r)-getsum(e.l-1);
            }else{
                ans[e.id]+=getsum(e.r)-getsum(e.l-1);
            }
        }
    }

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

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void transform(std::string&)':
selling_rna.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int f=0;f<s.size();f++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findpref(std::string)':
selling_rna.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findsuff(std::string)':
selling_rna.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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