Submission #1145142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145142		trandangquang	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	237 ms	202128 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define fi first
#define se second
#define ll long long
#define int long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if(x < y) {
            x = y;
            return true;
        }
        return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if(x > y) {
            x = y;
            return true;
        }
        return false;
    }

void solve();
int32_t main() {
    #define task "test"
    if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	cin.tie(0)->sync_with_stdio(0);

    solve();
}

const int N=1e5+5;

int n,m,tr[200];
string s[N];

struct Trie{
    struct Node{
        int ch[4],mn,mx;
        Node(){
            fill(begin(ch),end(ch),-1);
            mn=1e9,mx=0;
        }
    };

    vector<Node> t={Node()};
    void ahihi(int num, int val){
        t[num].mn=min(t[num].mn,val);
        t[num].mx=max(t[num].mx,val);
    }
    void add_string(string &s, int id){
        int p=0;
        for(char c:s){
            ahihi(p,id);
            int ct=tr[c];
            if(t[p].ch[ct]==-1){
                t[p].ch[ct]=sz(t);
                t.eb();
            }
            p=t[p].ch[ct];
        }
        ahihi(p,id);
    }
    ii getRange(string &s){
        int p=0;
        for(char c:s){
            int ct=tr[c];
            if(t[p].ch[ct]==-1) return {-1,-1};
            p=t[p].ch[ct];
        }
        return {t[p].mn, t[p].mx};
    }
} trie;

struct ReverseTrie{
    struct Node{
        int ch[4];
        vector<int> ids;
        Node(){
            fill(begin(ch),end(ch),-1);
        }
    };
    vector<Node> t={Node()};
    void ahihi(int num, int val){
        t[num].ids.eb(val);
    }
    void add_string(string &s, int id){
        int p=0;
        FORD(i,sz(s)-1,0){
            ahihi(p,id);
            int ct=tr[s[i]];
            if(t[p].ch[ct]==-1){
                t[p].ch[ct]=sz(t);
                t.eb();
            }
            p=t[p].ch[ct];
        }
        ahihi(p,id);
    }

    int query(string &s, int L, int R){
        int p=0;
        FORD(i,sz(s)-1,0){
            int ct=tr[s[i]];
            if(t[p].ch[ct]==-1) return 0;
            p=t[p].ch[ct];
        }

        int l=lower_bound(all(t[p].ids), L)-t[p].ids.begin(),
            r=upper_bound(all(t[p].ids), R)-t[p].ids.begin();

        return r-l;
    }
} revtrie;

void solve() {
    cin>>n>>m;
    FOR(i,1,n) cin>>s[i];
    sort(s+1,s+1+n);

    tr['A']=0; tr['U']=1; tr['G']=2; tr['C']=3;
    FOR(i,1,n){
        trie.add_string(s[i],i);
        revtrie.add_string(s[i],i);
    }

    FOR(i,1,m){
        string p,q; cin>>p>>q;
        ii range=trie.getRange(p);
        cout<<revtrie.query(q,range.fi,range.se)<<'\n';
    }
}

Compilation message (stderr)

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

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