oj.uz

Submission #1002474

# Submission time Handle Problem Language Result Execution time Memory
1002474 2024-06-19T15:07:46 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;
                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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31776 KB Output is correct
2 Correct 11 ms 31768 KB Output is correct
3 Correct 12 ms 31772 KB Output is correct
4 Correct 11 ms 31580 KB Output is correct
5 Correct 19 ms 31580 KB Output is correct
6 Correct 15 ms 31712 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 214 ms 253268 KB Output is correct
2 Correct 240 ms 241744 KB Output is correct
3 Correct 192 ms 170576 KB Output is correct
4 Correct 213 ms 164180 KB Output is correct
5 Correct 169 ms 244948 KB Output is correct
6 Correct 179 ms 248148 KB Output is correct
7 Correct 101 ms 47444 KB Output is correct
8 Correct 147 ms 168188 KB Output is correct
9 Correct 135 ms 148052 KB Output is correct
10 Correct 362 ms 142676 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 32972 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 31776 KB Output is correct
2 Correct 11 ms 31768 KB Output is correct
3 Correct 12 ms 31772 KB Output is correct
4 Correct 11 ms 31580 KB Output is correct
5 Correct 19 ms 31580 KB Output is correct
6 Correct 15 ms 31712 KB Output is correct
7 Correct 12 ms 31580 KB Output is correct
8 Correct 214 ms 253268 KB Output is correct
9 Correct 240 ms 241744 KB Output is correct
10 Correct 192 ms 170576 KB Output is correct
11 Correct 213 ms 164180 KB Output is correct
12 Correct 169 ms 244948 KB Output is correct
13 Correct 179 ms 248148 KB Output is correct
14 Correct 101 ms 47444 KB Output is correct
15 Correct 147 ms 168188 KB Output is correct
16 Correct 135 ms 148052 KB Output is correct
17 Correct 362 ms 142676 KB Output is correct
18 Execution timed out 1562 ms 32972 KB Time limit exceeded
19 Halted 0 ms 0 KB -