Submission #918893

#	Time	Username	Problem	Language	Result	Execution time	Memory
918893		phamducminh	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	221 ms	222216 KiB

selling_rna

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;






///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


    // file("tbrackets");







    long long t;


    // cin >> t;

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///


int val(char c) {
    switch(c) {
        case 'A': return 0;
        case 'G': return 1;
        case 'C': return 2;
        default: return 3;
    }
}


int n,q;


struct Trie {
    struct Node{

        Node* child[4];
        int cnt,exist,l,r;


        Node() {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
            cnt=exist==0;
            l=n; r=0;
        }
    };

    Node* root= new Node();

    void insert(string x, int id){
        Node* p=root;
        for (char ch: x){

            int c=val(ch);
            if (p->child[c]==nullptr){
                p->child[c]=new Node();
            }
            p=p->child[c];
            p->cnt++;
            p->l=min(p->l,id);
            p->r=max(p->r,id);

        }
        p->exist++;
    }


    pair<int,int> check(string s) {
        Node* p = root;
        pair<int,int> ans={0,n};
        for (auto f : s) {
            int c = val(f);
            if (p->child[c] == nullptr) return ans;
            p = p->child[c];

            ans.first=max(ans.first,p->l);
            ans.second=min(ans.second,p->r);


        }
        return ans;
    }
};


struct reverseTrie {
    struct Node{

        Node* child[4];
        int cnt,exist;
        vector<int> luu;


        Node() {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
            cnt=exist==0;
        }
    };

    Node* root= new Node();

    void insert(string x, int id){
        Node* p=root;
        reverse(all(x));

        for (char ch: x){

            int c=val(ch);
            if (p->child[c]==nullptr){
                p->child[c]=new Node();
            }
            p=p->child[c];
            p->cnt++;
            p->luu.push_back(id);

        }
        p->exist++;
    }


    int query(string s, pair<int,int> range) {
        Node* p = root;
        pair<int,int> ans={0,n};
        reverse(all(s));
        for (auto f : s) {
            int c = val(f);
            if (p->child[c] == nullptr) return 0;
            p = p->child[c];

            

        }

        int l=lower_bound(all(p->luu),range.first)-(p->luu).begin();
        int r=upper_bound(all(p->luu),range.second)-(p->luu).begin()-1;

        

        return r-l+1;
    }
};



Trie a;
reverseTrie b;

void solve(){

    
    
    string s[100009];

    cin >> n >> q;


    for (int i=1; i<=n; i++){


        cin >> s[i];


    }

    sort(s+1,s+n+1);

    for (int i=1; i<=n; i++) a.insert(s[i],i),b.insert(s[i],i);

    while (q--){


        string s1,s2;

        cin >> s1 >> s2;

        auto tam=a.check(s1);

        if (!tam.first) {cout << 0 << "\n"; continue;}


        cout << b.query(s2,tam) << "\n";
    }
    
        
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int reverseTrie::query(std::string, std::pair<int, int>)':
selling_rna.cpp:215:23: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  215 |         pair<int,int> ans={0,n};
      |                       ^~~
selling_rna.cpp: In constructor 'Trie::Node::Node()':
selling_rna.cpp:135:17: warning: '*<unknown>.Trie::Node::exist' is used uninitialized in this function [-Wuninitialized]
  135 |             cnt=exist==0;
      |                 ^~~~~

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