Submission #1002474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002474		nmts	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1562 ms	253268 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 pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#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'    
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
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 n , m;
string s[maxn];

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

struct Trie{

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

    Node* root;

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

    void add(string s , int id)
        {
            Node* p = root;
            for(int i=0 ; i<(int)s.size() ; ++i)
                {
                    int c = get_val(s[i]);
                    if (p -> child[c] == NULL) p -> child[c] = new Node;
                    p = p -> child[c];
                    minimize(p -> l , id);
                    maximize(p -> r , id);
                }

            p -> exits++;
        }

    pii get_range(string s)
        {
            Node* p = root;
            for (int i=0 ; i< (int)s.size() ; ++i)
                {
                    int c = get_val(s[i]);
                    if (p->child[c] == NULL) return {-1 , -1};
                    p = p->child[c];
                }
            return {p->l , p->r};
        }


};

struct RTrie{

    struct Node{
        Node* child[5];
        vector<int> exits;
        Node()
            {
                for (int i=1 ; i<=4 ; ++i) child[i] = NULL;
                exits.clear();
            }
    };

    Node* root;

    RTrie()
        {
            root = new Node;
        };

    void add(string s , int id)
        {
            Node* p = root;
            for (int i=0 ; i<(int)s.size() ; ++i)
                {
                    int c = get_val(s[i]);
                    if (p->child[c] == NULL) p->child[c] = new Node;
                    p = p->child[c];
                    p->exits.push_back(id);
                }   
           
        
        }

    int get_ans(string s , int u , int v)
        {
            Node* p = root;
            for (int i=0 ; i< (int)s.size() ; ++i)
                {
                    int c = get_val(s[i]);
                    if (p->child[c] == NULL) return 0;
                    p = p->child[c];
                }

            sort(p -> exits.begin() , p->exits.end());
            // for (int x : p->exits) cout << x << " " ; cout << endl;
            int l = lower_bound(p -> exits.begin() , p->exits.end() , u) - (p -> exits.begin());
            int r = upper_bound(p -> exits.begin() , p->exits.end() , v) - (p -> exits.begin()) - 1;

            return r - l + 1;
        }

};

void solve()
{

    cin >> n >> m ;

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

    sort(s+1 , s+n+1);
    
    Trie tr;
    RTrie Rtr;
    for (int i=1 ; i<=n ; ++i)
        {
            tr.add(s[i] , i);
            reverse(s[i].begin() , s[i].end());
            Rtr.add(s[i] , i);
        }

    while (m--)
        {
            string a , b ; cin >> a >> b;
            pii it = tr.get_range(a);
            // cout << it.fi << " " <<it.se << endl;
            reverse(b.begin() , b.end());
            if (it.fi == -1) cout << 0 << '\n';
            else cout << Rtr.get_ans(b , it.fi , it.se) << '\n';
        }

}


int32_t main()
{
    faster;
    
    solve();
    return 0;
} 

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