oj.uz

Submission #219405

# Submission time Handle Problem Language Result Execution time Memory
219405 2020-04-05T09:21:23 Z MKopchev Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 440 ms 322880 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,q;

struct info
{
    int nxt[26];
};

vector< info > trie;

int pointer=0;

vector< vector<int> > seen;

int create_info()
{
    seen.push_back({});

    info idle;
    for(int i=0;i<26;i++)
        idle.nxt[i]=-1;

    trie.push_back(idle);
    pointer++;

    //cout<<"create_info= "<<pointer-1<<endl;

    return pointer-1;
}

pair<string,int> inp[nmax];

void add(int id)
{

    int current=0;
    for(int i=0;i<inp[id].first.size();i++)
    {
        char c=inp[id].first[i];

        if(trie[current].nxt[c-'A']==-1)
        {
            int mem=create_info();
            trie[current].nxt[c-'A']=mem;
        }

        //cout<<trie[current].nxt[c-'A']<<endl;

        current=trie[current].nxt[c-'A'];

        seen[current].push_back(id);
    }
}
string sorted_strings[nmax];

string en;

int query(int l,int r)
{
    int current=0;
    for(int i=0;i<en.size();i++)
    {
        char c=en[i];

        if(trie[current].nxt[c-'A']==-1)return 0;
        else current=trie[current].nxt[c-'A'];
    }

    int u=lower_bound(seen[current].begin(),seen[current].end(),l)-seen[current].begin();
    int v=upper_bound(seen[current].begin(),seen[current].end(),r)-seen[current].begin();
    return v-u;
}
int ask()
{
    string st;
    cin>>st>>en;

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

    int l=lower_bound(sorted_strings+1,sorted_strings+n+1,st)-sorted_strings;
    st[st.size()-1]++;
    int r=lower_bound(sorted_strings+1,sorted_strings+n+1,st)-sorted_strings;r--;

    //cout<<"query "<<l<<" "<<r<<endl;

    if(l>r)return 0;
    return query(l,r);
}

int main()
{
    create_info();

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

    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>sorted_strings[i];

    sort(sorted_strings+1,sorted_strings+n+1);

    for(int i=1;i<=n;i++)
        inp[i]={sorted_strings[i],i};

    for(int i=1;i<=n;i++)
        reverse(inp[i].first.begin(),inp[i].first.end());

    for(int i=1;i<=n;i++)
        add(i);

    for(int i=1;i<=q;i++)
        printf("%i\n",ask());
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inp[id].first.size();i++)
                 ~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(int, int)':
selling_rna.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<en.size();i++)
                 ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 322880 KB Output is correct
2 Correct 432 ms 309208 KB Output is correct
3 Correct 79 ms 27648 KB Output is correct
4 Correct 78 ms 27136 KB Output is correct
5 Correct 350 ms 307032 KB Output is correct
6 Correct 365 ms 307444 KB Output is correct
7 Correct 67 ms 24568 KB Output is correct
8 Correct 298 ms 163264 KB Output is correct
9 Correct 261 ms 164672 KB Output is correct
10 Correct 223 ms 166976 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 8952 KB Output is correct
2 Correct 40 ms 9260 KB Output is correct
3 Correct 45 ms 8868 KB Output is correct
4 Correct 37 ms 8440 KB Output is correct
5 Correct 42 ms 8576 KB Output is correct
6 Correct 51 ms 8576 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 438 ms 322880 KB Output is correct
9 Correct 432 ms 309208 KB Output is correct
10 Correct 79 ms 27648 KB Output is correct
11 Correct 78 ms 27136 KB Output is correct
12 Correct 350 ms 307032 KB Output is correct
13 Correct 365 ms 307444 KB Output is correct
14 Correct 67 ms 24568 KB Output is correct
15 Correct 298 ms 163264 KB Output is correct
16 Correct 261 ms 164672 KB Output is correct
17 Correct 223 ms 166976 KB Output is correct
18 Correct 48 ms 8952 KB Output is correct
19 Correct 40 ms 9260 KB Output is correct
20 Correct 45 ms 8868 KB Output is correct
21 Correct 37 ms 8440 KB Output is correct
22 Correct 42 ms 8576 KB Output is correct
23 Correct 51 ms 8576 KB Output is correct
24 Correct 413 ms 309464 KB Output is correct
25 Correct 440 ms 309460 KB Output is correct
26 Correct 401 ms 309440 KB Output is correct
27 Correct 95 ms 27320 KB Output is correct
28 Correct 272 ms 57592 KB Output is correct
29 Correct 141 ms 16048 KB Output is correct