Submission #1267578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267578		dangheo	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	168 ms	187772 KiB

selling_rna

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmb = 1e5 + 69;
const ld pi = atan(1) * 4;

int n, m;
string s[mmb];
string p, q;

inline int getCode(char x){
    switch(x){
        case 'A': return 0;
        case 'C': return 1;
        case 'G': return 2;
        case 'U': return 3;
    }
}

struct TriePref{
    struct Node{
        vector <int> ids;
        Node *ch[4];
        Node(){fill(ch, ch + 4, nullptr);}
    };
    
    Node *root = new Node;
    
    void insert(int id){
        int l = s[id].length();
        Node *cur = root;
        for(int i = l - 1; i >= 0; --i){
            int d = getCode(s[id][i]);
            if(cur->ch[d] == nullptr)
                cur->ch[d] = new Node;
            
            cur = cur->ch[d];
            cur->ids.push_back(id);
        }
    }
    
    int countString(string &s, int l, int r){
        Node *cur = root;
        
        for(char i : s){
            int d = getCode(i);
            if(cur->ch[d] == nullptr)
                return 0;
            
            cur = cur->ch[d];
        }
        
        vector <int> &a = cur->ids;
        return upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);
    }
} trp;

struct TrieSuf{
    struct Node{
        Node *ch[4];
        int mn = 0, mx = 0;
        Node(){fill(ch, ch + 4, nullptr);}
    };
    
    Node *root = new Node;
    
    void insert(int id){
        int l = s[id].length();
        Node *cur = root;
        for(int i = 0; i < l; ++i){
            int d = getCode(s[id][i]);
            if(cur->ch[d] == nullptr)
                (cur->ch[d] = new Node)->mn = id;
            
            cur = cur->ch[d];
            cur->mx = id;
        }
    }
    
    pair <int, int> searchRange(string &s){
        Node *cur = root;
        for(char i : s){
            int d = getCode(i);
            if(cur->ch[d] == nullptr)
                return make_pair(0, 0);
            
            cur = cur->ch[d];
        }
        
        return make_pair(cur->mn, cur->mx);
    }
} trf;

void readData(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
    }
    
    sort(s + 1, s + n + 1);
}

void solve(){
    for(int i = 1; i <= n; ++i){
        trp.insert(i);
        trf.insert(i);
    }
    
    for(int i = 1; i <= m; ++i){
        cin >> p >> q;
        reverse(q.begin(), q.end());
        pair <int, int> rng = trf.searchRange(q);
        cout << trp.countString(p, rng.first, rng.second) << "\n";
    }
}

#define filename "test"

int hyathu(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    #ifdef dangheo
    freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    #else
    //freopen(filename".INP", "r", stdin);
    //freopen(filename".OUT", "w", stdout);
    #endif
    
    readData();
    solve();
    
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int getCode(char)':
selling_rna.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

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