Submission #476371

#	Time	Username	Problem	Language	Result	Execution time	Memory
476371		nicolaalexandra	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	732 ms	642240 KiB

selling_rna

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

vector <char> s[DIM];
char p[DIM],q[DIM],w[DIM],a[DIM];
int poz[DIM],lg[DIM];
int n,m,i,j,l,r,sol;


struct trie{
    int l,r;
    trie *f[27];
    trie(){
        l = INF, r = 0;
        for (int i=0;i<26;i++)
            f[i] = 0;
    }
};

trie *rad1 = new trie;


struct trie2{
    vector <int> v;
    trie2 *f[27];
    trie2(){
        for (int i=0;i<26;i++)
            f[i] = 0;
    }
};

trie2 *rad2 = new trie2;


void add (trie *rad, char *s){
    if (*s == NULL){
        rad->l = min (rad->l,i);
        rad->r = max (rad->r,i);
        //rad->l = rad->r = i;
    } else {
        if (rad->f[*s-'A'] == 0)
            rad->f[*s-'A'] = new trie;

        add (rad->f[*s-'A'],s+1);

    }
}

void dfs (trie *rad){
    if (rad == NULL)
        return;
    for (int i=0;i<26;i++){
        if (rad->f[i]){
            dfs (rad->f[i]);
            rad->l = min (rad->l,rad->f[i]->l);
            rad->r = max (rad->r,rad->f[i]->r);
        }
    }
}

void dfs2 (trie2 *rad){
    if (rad == NULL)
        return;

    sort (rad->v.begin(),rad->v.end());

    for (int i=0;i<26;i++)
        if (rad->f[i])
            dfs2 (rad->f[i]);
}


void add2 (trie2 *rad, char *s){
    rad->v.push_back(i);
    if (*s == NULL){
        return;
    } else {
        if (rad->f[*s-'A'] == NULL)
            rad->f[*s-'A'] = new trie2;

        add2 (rad->f[*s-'A'],s+1);
    }
}

void query (trie *rad, char *s){
    if (*s == NULL)
        l = rad->l, r = rad->r;
    else {

        if (rad->f[*s-'A'] == NULL)
            return;

        query (rad->f[*s-'A'],s+1);
    }

}

void query2 (trie2 *rad, char *s){
    if (*s == NULL){

        /// cate elemente din vectoru asta sunt intre l si r

        vector <int> :: iterator it = lower_bound(rad->v.begin(),rad->v.end(),l);

        if (it == rad->v.end())
            return;

        vector <int> :: iterator it2 = upper_bound(rad->v.begin(),rad->v.end(),r);
        it2--;

        sol = it2 - it + 1;

        /*for (int i=0;i<rad->v.size();i++)
            if (rad->v[i] >= l && rad->v[i] <= r)
                sol++;
        */

        return;
    } else {
        if (rad->f[*s-'A'] == NULL)
            return;

        query2 (rad->f[*s-'A'],s+1);
    }
}


inline int cmp (int a, int b){

    for (int i=0;i<min(lg[a],lg[b]);i++)
        if (s[a][i] != s[b][i])
            return s[a][i] < s[b][i];

    return lg[a] < lg[b];

}

void copiere (char w[], vector<char> v){
    for (int i=0;i<v.size();i++)
        w[i] = v[i];
    w[v.size()] = NULL;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>a;
        lg[i] = strlen(a);

        for (j=0;j<lg[i];j++)
            s[i].push_back(a[j]);

        poz[i] = i;
    }

    sort (poz+1,poz+n+1,cmp);

    for (i=1;i<=n;i++){
        copiere (w,s[poz[i]]);
        add (rad1,w);
    }

    dfs (rad1);


    for (i=1;i<=n;i++){
        reverse (s[poz[i]].begin(),s[poz[i]].end());
        copiere (w,s[poz[i]]);
        add2 (rad2,w);
    }

    dfs2 (rad2);


    for (;m--;){

        cin>>p>>q;

        l = r = 0;
        query(rad1,p);
        if (!l){
            cout<<"0\n";
            continue;
        }

        reverse (q,q+strlen(q));
        sol = 0;
        query2 (rad2,q);

        cout<<sol<<"\n";
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(trie*, char*)':
selling_rna.cpp:38:15: warning: NULL used in arithmetic [-Wpointer-arith]
   38 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void add2(trie2*, char*)':
selling_rna.cpp:77:15: warning: NULL used in arithmetic [-Wpointer-arith]
   77 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void query(trie*, char*)':
selling_rna.cpp:88:15: warning: NULL used in arithmetic [-Wpointer-arith]
   88 |     if (*s == NULL)
      |               ^~~~
selling_rna.cpp: In function 'void query2(trie2*, char*)':
selling_rna.cpp:101:15: warning: NULL used in arithmetic [-Wpointer-arith]
  101 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void copiere(char*, std::vector<char>)':
selling_rna.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for (int i=0;i<v.size();i++)
      |                  ~^~~~~~~~~
selling_rna.cpp:143:19: warning: converting to non-pointer type 'char' from NULL [-Wconversion-null]
  143 |     w[v.size()] = NULL;
      |                   ^~~~

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