Submission #1067725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067725		nmts	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	827 ms	228948 KiB

selling_rna

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define ll long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

int get_val(char ch)
{
    return (ch == 'A' ? 0 : ch == 'G' ? 1 : ch == 'C' ? 2 : 3);
}

struct Trie{

    struct Node
        {
            int l , r;
            Node* child[4];
            int exits;


            Node()
                {
                    l = INF , r = -INF;
                    for (int i = 0 ; i < 4 ; ++i) child[i] = NULL;
                    exits = 0;
                }

        };
    
    Node* root;

    Trie()
        {
            root = new Node();
        };


    void add(string s , int id)
        {   

            Node* p = root;

            for (int i = 0 ; i < s.size() ; ++i)
                {
                    int c = get_val(s[i]);

                    if (p->child[c] == NULL) p -> child[c] = new Node();
                    p = p -> child[c];
                    p->l = min(p->l , id);
                    p->r = max(p->r , id);

                }
            p->exits++;
        }

    pii get_range(string s)
        {
            
            Node*p = root;

            for (int i = 0 ; i < s.size() ; ++i)
                {
                    int c = get_val(s[i]);

                    if (p -> child[c] == NULL) return make_pair(-1 , -1);

                    p = p -> child[c];

                }
            return make_pair(p -> l , p -> r);
        }

};



struct RTrie{

    struct Node
        {
            Node* child[4];
            vector<int> id;


            Node()
                {
                    for (int i = 0 ; i < 4 ; ++i) child[i] = NULL;
                    id.clear();
                }

        };
    
    Node* root;

    RTrie()
        {
            root = new Node();
        };


    void add(string s , int id)
        {   

            Node* p = root;

            for (int i = 0 ; i < s.size() ; ++i)
                {
                    int c = get_val(s[i]);

                    if (p->child[c] == NULL) p -> child[c] = new Node();
                    p = p -> child[c];
                    p->id.push_back(id);
                }
           
        }

    int get_ans(string  s, int u , int v)
        {
            
            Node*p = root;

            for (int i = 0 ; i < s.size() ; ++i)
                {
                    int c = get_val(s[i]);

                    if (p -> child[c] == NULL) return 0;

                    p = p -> child[c];

                }

            if (!is_sorted(p -> id.begin() , p -> id.end()))
                sort(p->id.begin() , p->id.end());
            
            int l = lower_bound(p->id.begin() , p->id.end() , u) - p->id.begin();
            int r = upper_bound(p->id.begin() , p->id.end() , v) - p->id.begin();

            return r - l;

        }

};

int n , m;

string s[maxn];

Trie tr;
RTrie Rtr;

void solve()
{

    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)
        {
            tr.add(s[i] , i);
            reverse(s[i].begin() , s[i].end());
            Rtr.add(s[i] , i);
        }
    
    for (int i = 1 ; i <= m ; ++i) 
        {
            string a , b ; cin >> a >> b;
            
            pii tmp = tr.get_range(a);

            // cout << tmp.fi << " " << tmp.se << endl;

            if (tmp.fi == -1) cout << 0 << endl;
            else
            {

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

                cout << Rtr.get_ans(b , tmp.fi , tmp.se) << endl;

            }

        }

}


int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
} 

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add(std::string, int)':
selling_rna.cpp:76:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i = 0 ; i < s.size() ; ++i)
      |                              ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get_range(std::string)':
selling_rna.cpp:94:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for (int i = 0 ; i < s.size() ; ++i)
      |                              ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void RTrie::add(std::string, int)':
selling_rna.cpp:139:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for (int i = 0 ; i < s.size() ; ++i)
      |                              ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int RTrie::get_ans(std::string, int, int)':
selling_rna.cpp:155:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             for (int i = 0 ; i < s.size() ; ++i)
      |                              ~~^~~~~~~~~~

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