Submission #1079158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079158		vnm06	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	210 ms	94336 KiB

selling_rna

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

inline int conv_letter(char c)
{
    if(c=='A') return 0;
    if(c=='C') return 1;
    if(c=='G') return 2;
    return 3;
}

struct vypros
{
    string p, q;
    int nom;

    vypros() {}
};

int n, m;
int ans[100005];
vypros queries[100005];

string s[100005];


int brstates=1;
int states[2000005][4];
int be[2000005], en[2000005];

void addword(int id)
{
    int currstate=1;
    for(int j=s[id].size()-1; j>=0; j--)
    {
        int trns=conv_letter(s[id][j]);
        if(!states[currstate][trns])
        {
            states[currstate][trns]=brstates+1;
            brstates++;
        }
        currstate=states[currstate][trns];
    }
}

int curr_count=1;

void count_states(int pos)
{
    be[pos]=curr_count;
    for(int i=0; i<4; i++)
    {
        if(states[pos][i])
        {
            curr_count++;
            count_states(states[pos][i]);
        }
    }
    en[pos]=curr_count;
}

vector<int> izv[100005];
vector<int> sub[100005];
pair<string, int> trikche[300005];


int fenw[2000005];

int query(int pos)
{
    int res=0;
    while(pos)
    {
        res+=fenw[pos];
        pos-=(pos&(-pos));
    }
    return res;
}

int query(int le, int ri)
{
    return query(ri)-query(le-1);
}

void update(int pos)
{
    while(pos<=brstates)
    {
        fenw[pos]++;
        pos+=(pos&(-pos));
    }
}

int query_suf(int id)
{
    int currstate=1;
    for(int j=queries[id].q.size()-1; j>=0; j--)
    {
        int trns=conv_letter(queries[id].q[j]);
        if(!states[currstate][trns]) return 0;
        currstate=states[currstate][trns];
    }
    ///if(id==4) cout,,
    return query(be[currstate], en[currstate]);
    
}

void update_word(int id)
{
    int currstate=1;
    for(int j=s[id].size()-1; j>=0; j--)
    {
        int trns=conv_letter(s[id][j]);
        currstate=states[currstate][trns];
    }
    update(be[currstate]);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>s[i];
    sort(s+1, s+n+1);
    for(int i=1; i<=n; i++) addword(i);
    count_states(1);
    /**for(int i=1; i<=brstates; i++)
    {
        cout<<be[i]<<" "<<en[i]<<endl;
        cout<<states[i][0]<<" "<<states[i][1]<<" "<<states[i][2]<<" "<<states[i][3]<<endl;
    }*/
    for(int i=1; i<=m; i++)
    {
        cin>>queries[i].p>>queries[i].q;
        queries[i].nom=i;
    }
    for(int i=0; i<n; i++) trikche[i]={s[i+1], 1000000000};
    for(int i=0; i<m; i++) 
    {
        trikche[n+2*i]={queries[i+1].p, -(i+1)};
        trikche[n+2*i+1]={queries[i+1].p+'z', i+1};
    }
    sort(trikche, trikche+n+2*m);
    int brdum=0;
    for(int i=0; i<n+2*m; i++)
    {
        //cout<<trikche[i].first<<endl;
        if(trikche[i].second==1000000000) brdum++;
        else if(trikche[i].second<0) izv[brdum].push_back(-trikche[i].second);
        else sub[brdum].push_back(trikche[i].second);
    }
    for(int i=0; i<=n; i++)
    {
        //cout<<"otg "<<ans[4]<<endl;
        //cout<<i<<endl;
        //cout<<"izv: ";
        for(int j=0; j<izv[i].size(); j++) ans[izv[i][j]]-=query_suf(izv[i][j]); //cout<<izv[i][j]<<" ";}
        //cout<<"\nsub: ";
        for(int j=0; j<sub[i].size(); j++) ans[sub[i][j]]+=query_suf(sub[i][j]); //cout<<sub[i][j]<<" ";}
        //cout<<endl;
        if(i==n) break;
        update_word(i+1);
    }
    for(int i=1; i<=m; i++) cout<<ans[i]<<endl;
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(int j=0; j<izv[i].size(); j++) ans[izv[i][j]]-=query_suf(izv[i][j]); //cout<<izv[i][j]<<" ";}
      |                      ~^~~~~~~~~~~~~~
selling_rna.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int j=0; j<sub[i].size(); j++) ans[sub[i][j]]+=query_suf(sub[i][j]); //cout<<sub[i][j]<<" ";}
      |                      ~^~~~~~~~~~~~~~

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