oj.uz

Submission #1067725

# Submission time Handle Problem Language Result Execution time Memory
1067725 2024-08-21T02:07:46 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 827 ms 228948 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31580 KB Output is correct
2 Correct 15 ms 31580 KB Output is correct
3 Correct 14 ms 31576 KB Output is correct
4 Correct 15 ms 31576 KB Output is correct
5 Correct 15 ms 31580 KB Output is correct
6 Correct 14 ms 31712 KB Output is correct
7 Correct 14 ms 31580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 222780 KB Output is correct
2 Correct 214 ms 212780 KB Output is correct
3 Correct 139 ms 170324 KB Output is correct
4 Correct 136 ms 163924 KB Output is correct
5 Correct 176 ms 225876 KB Output is correct
6 Correct 175 ms 228948 KB Output is correct
7 Correct 59 ms 47444 KB Output is correct
8 Correct 146 ms 157268 KB Output is correct
9 Correct 134 ms 138836 KB Output is correct
10 Correct 121 ms 133684 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 32968 KB Output is correct
2 Correct 84 ms 33108 KB Output is correct
3 Correct 128 ms 33000 KB Output is correct
4 Correct 175 ms 32852 KB Output is correct
5 Correct 249 ms 33108 KB Output is correct
6 Correct 363 ms 32880 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31580 KB Output is correct
2 Correct 15 ms 31580 KB Output is correct
3 Correct 14 ms 31576 KB Output is correct
4 Correct 15 ms 31576 KB Output is correct
5 Correct 15 ms 31580 KB Output is correct
6 Correct 14 ms 31712 KB Output is correct
7 Correct 14 ms 31580 KB Output is correct
8 Correct 194 ms 222780 KB Output is correct
9 Correct 214 ms 212780 KB Output is correct
10 Correct 139 ms 170324 KB Output is correct
11 Correct 136 ms 163924 KB Output is correct
12 Correct 176 ms 225876 KB Output is correct
13 Correct 175 ms 228948 KB Output is correct
14 Correct 59 ms 47444 KB Output is correct
15 Correct 146 ms 157268 KB Output is correct
16 Correct 134 ms 138836 KB Output is correct
17 Correct 121 ms 133684 KB Output is correct
18 Correct 656 ms 32968 KB Output is correct
19 Correct 84 ms 33108 KB Output is correct
20 Correct 128 ms 33000 KB Output is correct
21 Correct 175 ms 32852 KB Output is correct
22 Correct 249 ms 33108 KB Output is correct
23 Correct 363 ms 32880 KB Output is correct
24 Correct 189 ms 189012 KB Output is correct
25 Correct 225 ms 189268 KB Output is correct
26 Correct 188 ms 187076 KB Output is correct
27 Correct 208 ms 147124 KB Output is correct
28 Correct 827 ms 66820 KB Output is correct
29 Correct 213 ms 40204 KB Output is correct