Submission #1297355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297355		kqhuy2009	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	186 ms	103708 KiB

selling_rna

#include <bits/stdc++.h>
#define ll int
#define INF (ll)1e9+1
#define bit(mask, id) ((mask >> id) & 1LL)
#define pb push_back
#define el '\n'
#define ft first
#define sc second
#define ii pair<ll,ll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, l, r) for(int i = (l); i >= (r); --i)
#define str string
#define all(a,i) memset(a,i,sizeof(a))
#define al(a) a.begin(),a.end()
/////////////////////////////

const long long oo = 1e18;
const int N = 3e5 + 9;

using namespace std;

struct TRIE{
    struct Node{
        ll l,r;
        vector<ll>exist;
        ll child[26];
    };
    Node node[N];
    ll curnode;
    ll new_node()
    {
        ++curnode;
        node[curnode].l = INF;
        node[curnode].r = 0;
        all(node[curnode].child,-1);
        node[curnode].exist.clear();
        return curnode;
    }
    TRIE(){
        curnode = -1;
        new_node();
    }
    void add(str s, ll id)
    {
        ll pos = 0;
        for(auto x:s)
        {
            ll c = x-'A';
            if(node[pos].child[c]==-1)
            {
                node[pos].child[c] = new_node();
            }
            pos = node[pos].child[c];

            node[pos].l = min(node[pos].l,id);
            node[pos].r = max(node[pos].r,id);
            //cout<<pos<<' '<<node[pos].l<<' '<<node[pos].r<<el;
            node[pos].exist.pb(id);
        }
    }
    bool fi(str s)
    {
        ll pos = 0;
        for(auto x:s)
        {
            ll c = x-'A';
            if(node[pos].child[c]==-1) return 0;
            pos = node[pos].child[c];
        }
        return 1;
    }
    vector<ll>suffix(str s)
    {
        vector<ll>ans;
        if(!fi(s)) return ans;
        ll pos = 0;
        for(auto x:s)
        {
            ll c = x-'A';
            pos = node[pos].child[c];
        }
        return node[pos].exist;
    }
    ii prefix(str s)
    {
        if(!fi(s)) return {0,0};
        ll pos = 0;
        for(auto x:s)
        {
            ll c = x-'A';
            pos = node[pos].child[c];
        }
        return {node[pos].l, node[pos].r};
    }
};
TRIE pre, suf;
str a[N];
ll n,Q;
ll Count(vector<ll>&v, ll l, ll r)
{
    ll L = lower_bound(al(v),l)-v.begin();
    ll R = upper_bound(al(v),r)-v.begin();
    //cout<<L<<' '<<R<<el;
    return R-L;
}
signed main()
{
    #define TASK "rna"
    if(fopen(TASK ".inp","r")) {
        freopen (TASK ".inp","r",stdin);
        freopen (TASK ".out","w",stdout);
        //freopen (TASK ".ans","w",stdout);
    }

//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);

    cin>>n>>Q;
    FOR(i,1,n) cin>>a[i];
    sort(a+1,a+1+n);
//    FOR(i,1,n) cout<<a[i]<<el;
    FOR(i,1,n)
    {
        pre.add(a[i],i);
        str t = a[i];
        reverse(al(t));

        suf.add(t,i);
        //cout<<a[i]<<' '<<t<<el;
    }

    FOR(i,1,Q)
    {
        str p,q; cin>>p>>q;
//        cout<<p<<' '<<q<<el;
        reverse(al(q));
        auto [l,r] = pre.prefix(p);
        vector<ll>ans = suf.suffix(q);
//        cout<<l<<' '<<r<<el;
//        for(auto x:ans) cout<<x<<' ';
//        cout<<el;
        //ans.pb(INF);
        cout<<Count(ans,l,r)<<el;
    }

    return 0;
}

Compilation message (stderr)

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

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