oj.uz

Submission #1002489

# Submission time Handle Problem Language Result Execution time Memory
1002489 2024-06-19T15:15:56 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 428 ms 253292 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 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;
            }
        
    };

    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;
            }
    };

    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];
                }

             if (!is_sorted(p->exits.begin(), p->exits.end())) {
            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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 253292 KB Output is correct
2 Correct 186 ms 241824 KB Output is correct
3 Correct 123 ms 170628 KB Output is correct
4 Correct 121 ms 164068 KB Output is correct
5 Correct 164 ms 245072 KB Output is correct
6 Correct 204 ms 248144 KB Output is correct
7 Correct 56 ms 47444 KB Output is correct
8 Correct 146 ms 168152 KB Output is correct
9 Correct 121 ms 148012 KB Output is correct
10 Correct 108 ms 142672 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 32976 KB Output is correct
2 Correct 74 ms 33108 KB Output is correct
3 Correct 81 ms 32996 KB Output is correct
4 Correct 93 ms 32848 KB Output is correct
5 Correct 129 ms 33020 KB Output is correct
6 Correct 183 ms 32908 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 14 ms 31576 KB Output is correct
4 Correct 12 ms 31580 KB Output is correct
5 Correct 12 ms 31608 KB Output is correct
6 Correct 12 ms 31580 KB Output is correct
7 Correct 12 ms 31580 KB Output is correct
8 Correct 184 ms 253292 KB Output is correct
9 Correct 186 ms 241824 KB Output is correct
10 Correct 123 ms 170628 KB Output is correct
11 Correct 121 ms 164068 KB Output is correct
12 Correct 164 ms 245072 KB Output is correct
13 Correct 204 ms 248144 KB Output is correct
14 Correct 56 ms 47444 KB Output is correct
15 Correct 146 ms 168152 KB Output is correct
16 Correct 121 ms 148012 KB Output is correct
17 Correct 108 ms 142672 KB Output is correct
18 Correct 349 ms 32976 KB Output is correct
19 Correct 74 ms 33108 KB Output is correct
20 Correct 81 ms 32996 KB Output is correct
21 Correct 93 ms 32848 KB Output is correct
22 Correct 129 ms 33020 KB Output is correct
23 Correct 183 ms 32908 KB Output is correct
24 Correct 183 ms 214052 KB Output is correct
25 Correct 191 ms 214064 KB Output is correct
26 Correct 163 ms 211796 KB Output is correct
27 Correct 169 ms 147268 KB Output is correct
28 Correct 428 ms 70160 KB Output is correct
29 Correct 135 ms 40140 KB Output is correct