Submission #1297399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297399		kqhuy2009	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	240 ms	278816 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 = 2e5 + 9;

using namespace std;

struct TRIE{
    struct Node{
        ll l,r;
        vector<ll>exist;
        Node* child[4];
        Node(){
            l = INF, r = 0;
            FOR(i,0,3) child[i] = NULL;
        }
    };
    Node* root;
    TRIE(){
        root  = new Node();
    }
    void add(str &s, ll id)
    {
        Node* pos = root;
        for(auto x:s)
        {
            ll c = x-'A';
            if(pos->child[c]==NULL)
            {
                pos->child[c] = new Node();
            }
            pos = pos->child[c];

            pos->l = min(pos->l,id);
            pos->r = max(pos->r,id);
            pos->exist.pb(id);
        }
    }
    bool fi(str &s)
    {
        Node* pos = root;
        for(auto x:s)
        {
            ll c = x-'A';
            if(pos->child[c]==NULL) return 0;
            pos = pos->child[c];
        }
        return 1;
    }
    vector<ll>suffix(str &s)
    {
        vector<ll>ans;
        if(!fi(s)) return ans;
        Node* pos = root;
        for(auto x:s)
        {
            ll c = x-'A';
            pos = pos->child[c];
        }
        return pos->exist;
    }
    ii prefix(str &s)
    {
        if(!fi(s)) return {0,0};
        Node* pos = root;
        for(auto x:s)
        {
            ll c = x-'A';
            pos = pos->child[c];
        }
        return {pos->l, pos->r};
    }
};
TRIE pre, suf;
str a[N];
ll n,Q;
void en(str &s)
{
    for(auto &x:s)
    {
        if(x=='G') x='B';
        else if(x=='U') x='D';
    }
}
ll Count(vector<ll>&v, ll l, ll r)
{
    if(v.empty() || l==0 || r==0) return 0;
    ll L = lower_bound(al(v),l)-v.begin();
    ll R = upper_bound(al(v),r)-v.begin();
    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], en(a[i]);
    sort(a+1,a+1+n);

    FOR(i,1,n)
    {
        pre.add(a[i],i);
        str t = a[i];
        reverse(al(t));

        suf.add(t,i);

    }

    FOR(i,1,Q)
    {
        str p,q; cin>>p>>q;
        en(p);
        en(q);

        reverse(al(q));

        auto [l,r] = pre.prefix(p);
        vector<ll>ans = suf.suffix(q);

        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: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40