Submission #1169405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169405		pemguimn	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	459 ms	623500 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 5, INF = 1e9 + 7;  

int n, m;
string s[N];

struct node1{
    node1 *child[26];
    int mx, mn;

    node1(){
        for(int i = 0; i < 26; i++) child[i] = nullptr;
        mx = 0, mn = INF;
    }
};

node1 *r1 = new node1();

struct node2{
    node2 *child[26];
    vector<int> v;

    node2(){
        for(int i = 0; i < 26; i++) child[i] = nullptr;
        v.clear();
    }

    int cnt(pii range){
        if(v.empty()) return 0;
        return upper_bound(v.begin(), v.end(), range.second) - lower_bound(v.begin(), v.end(), range.first);
    }
};

node2 *r2 = new node2();

void add(node1 *p, const string &s, int id){
    for(char c : s){
        int nxt = c - 'A';
        if(!p -> child[nxt]) p -> child[nxt] = new node1();
        p = p -> child[nxt];
        p -> mx = max(p -> mx, id);
        p -> mn = min(p -> mn, id);
    }
}

void add1(node2 *p, const string &s, int id){
    for(char c : s){
        int nxt = c - 'A';
        if(!p -> child[nxt]) p -> child[nxt] = new node2();
        p = p -> child[nxt];
        p -> v.push_back(id);
    }
}

pii query(node1 *p, const string &pre){
    for(char c : pre){  
        int nxt = c - 'A';
        if(!p -> child[nxt]) return {-1, -1};
        p = p -> child[nxt];
    }
    return {p -> mn, p -> mx};
}

int query1(node2 *p, const string &pre, pii range){
    for(char c : pre){  
        int nxt = c - 'A';
        if(!p -> child[nxt]) return 0;
        p = p -> child[nxt];
    }
    return p -> cnt(range);
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }
    sort(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++){
        add(r1, s[i], i);
        reverse(s[i].begin(), s[i].end());
        add1(r2, s[i], i);
    }
    for(int i = 1; i <= m; i++){
        string p, q; cin >> p >> q;
        reverse(q.begin(), q.end());
        pii range = query(r1, p);
        int ans = 0;
        if(range.first != -1) ans = query1(r2, q, range);
        cout << ans << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    #define task "RNA"
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }

    solve();  
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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