oj.uz

Submission #1079158

# Submission time Handle Problem Language Result Execution time Memory
1079158 2024-08-28T11:23:48 Z vnm06 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 210 ms 94336 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27228 KB Output is correct
2 Correct 11 ms 27100 KB Output is correct
3 Correct 12 ms 26972 KB Output is correct
4 Correct 11 ms 26972 KB Output is correct
5 Correct 11 ms 27104 KB Output is correct
6 Correct 11 ms 26972 KB Output is correct
7 Correct 11 ms 26916 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94336 KB Output is correct
2 Correct 80 ms 92500 KB Output is correct
3 Correct 46 ms 36624 KB Output is correct
4 Correct 44 ms 35780 KB Output is correct
5 Correct 88 ms 67924 KB Output is correct
6 Correct 80 ms 68420 KB Output is correct
7 Correct 51 ms 43604 KB Output is correct
8 Correct 76 ms 63904 KB Output is correct
9 Correct 70 ms 61152 KB Output is correct
10 Correct 49 ms 53072 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28500 KB Output is correct
2 Correct 41 ms 27984 KB Output is correct
3 Correct 51 ms 28240 KB Output is correct
4 Correct 39 ms 27984 KB Output is correct
5 Correct 49 ms 27984 KB Output is correct
6 Correct 51 ms 28244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27228 KB Output is correct
2 Correct 11 ms 27100 KB Output is correct
3 Correct 12 ms 26972 KB Output is correct
4 Correct 11 ms 26972 KB Output is correct
5 Correct 11 ms 27104 KB Output is correct
6 Correct 11 ms 26972 KB Output is correct
7 Correct 11 ms 26916 KB Output is correct
8 Correct 81 ms 94336 KB Output is correct
9 Correct 80 ms 92500 KB Output is correct
10 Correct 46 ms 36624 KB Output is correct
11 Correct 44 ms 35780 KB Output is correct
12 Correct 88 ms 67924 KB Output is correct
13 Correct 80 ms 68420 KB Output is correct
14 Correct 51 ms 43604 KB Output is correct
15 Correct 76 ms 63904 KB Output is correct
16 Correct 70 ms 61152 KB Output is correct
17 Correct 49 ms 53072 KB Output is correct
18 Correct 54 ms 28500 KB Output is correct
19 Correct 41 ms 27984 KB Output is correct
20 Correct 51 ms 28240 KB Output is correct
21 Correct 39 ms 27984 KB Output is correct
22 Correct 49 ms 27984 KB Output is correct
23 Correct 51 ms 28244 KB Output is correct
24 Correct 104 ms 86432 KB Output is correct
25 Correct 120 ms 87656 KB Output is correct
26 Correct 89 ms 85152 KB Output is correct
27 Correct 56 ms 36436 KB Output is correct
28 Correct 210 ms 51584 KB Output is correct
29 Correct 151 ms 30800 KB Output is correct