oj.uz

Submission #1002487

# Submission time Handle Problem Language Result Execution time Memory
1002487 2024-06-19T15:15:05 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 253268 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];
                }

            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 31576 KB Output is correct
2 Correct 13 ms 31772 KB Output is correct
3 Correct 15 ms 31680 KB Output is correct
4 Correct 12 ms 31580 KB Output is correct
5 Correct 12 ms 31580 KB Output is correct
6 Correct 12 ms 31580 KB Output is correct
7 Correct 13 ms 31888 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 253268 KB Output is correct
2 Correct 203 ms 241800 KB Output is correct
3 Correct 187 ms 170548 KB Output is correct
4 Correct 201 ms 164180 KB Output is correct
5 Correct 169 ms 244904 KB Output is correct
6 Correct 176 ms 248148 KB Output is correct
7 Correct 112 ms 47308 KB Output is correct
8 Correct 144 ms 168260 KB Output is correct
9 Correct 125 ms 148008 KB Output is correct
10 Correct 303 ms 142672 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 32728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB Output is correct
2 Correct 13 ms 31772 KB Output is correct
3 Correct 15 ms 31680 KB Output is correct
4 Correct 12 ms 31580 KB Output is correct
5 Correct 12 ms 31580 KB Output is correct
6 Correct 12 ms 31580 KB Output is correct
7 Correct 13 ms 31888 KB Output is correct
8 Correct 197 ms 253268 KB Output is correct
9 Correct 203 ms 241800 KB Output is correct
10 Correct 187 ms 170548 KB Output is correct
11 Correct 201 ms 164180 KB Output is correct
12 Correct 169 ms 244904 KB Output is correct
13 Correct 176 ms 248148 KB Output is correct
14 Correct 112 ms 47308 KB Output is correct
15 Correct 144 ms 168260 KB Output is correct
16 Correct 125 ms 148008 KB Output is correct
17 Correct 303 ms 142672 KB Output is correct
18 Execution timed out 1567 ms 32728 KB Time limit exceeded
19 Halted 0 ms 0 KB -