Submission #1267452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267452		4o2a	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	185 ms	97096 KiB

selling_rna

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "test"
using namespace std;
typedef long long ll;

constexpr int S = 1300, maxn = 1e5;
int pfsz[maxn];
map<char, char> M = {{'A', 'A'}, {'G', 'B'}, {'C', 'C'}, {'U', 'D'}};

struct query
{
    int l, r, idx, res = 0;
    bool operator<(const query &q)
    {
        if (pfsz[l]/S == pfsz[q.l]/S)
            return r < q.r;
        return l < q.l;
    }
};

struct node
{
    node *child[4];
    int cnt;
    node()
    {
        for (int i = 0; i < 4; ++i)
            child[i] = nullptr;
        cnt = 0;
    }
} *root = new node();

void add(string &s)
{
    node *p = root;
    for (char &c: s)
    {
        if (!p->child[c - 'A'])
            p->child[c - 'A'] = new node();
        p = p->child[c - 'A'];
        p->cnt++;
    }
}

bool rmv(node *p, string &s, int i)
{
    if (i < s.size() && rmv(p->child[s[i] - 'A'], s, i+1))
        p->child[s[i] - 'A'] = nullptr;
    p->cnt--;
    if (p->cnt == 0)
    {
        delete p;
        return true;
    }
    return false;
}

void rmv(string &s){rmv(root, s, 0);}

int cntpref(string &s)
{
    node *p = root;
    for (char &c: s)
    {
        if (p->child[c - 'A'] == nullptr)
            return 0;
        p = p->child[c - 'A'];
    }
    return p->cnt;
}

void solve()
{
    int n, m; cin>>n>>m;
    vector<string> S(n), X(m), Y(m);
    vector<query> Q(m);
    for (int i = 0; i < n; ++i)
    {
        cin>>S[i];
        for (char &c: S[i])
            c = M[c];
        pfsz[i] = (i == 0 ? 0 : pfsz[i-1]) + S[i].size();
    }
    sort(S.begin(), S.end());
    for (int i = 0; i < m; ++i)
    {
        cin>>X[i]>>Y[i];
        for (char &c: X[i])
            c = M[c];
        for (char &c: Y[i])
            c = M[c];
        Q[i].l = lower_bound(S.begin(), S.end(), X[i]) - S.begin();
        Q[i].r = upper_bound(S.begin(), S.end(), X[i] + 'Z') - S.begin() - 1;
        Q[i].idx = i;
    }
    sort(Q.begin(), Q.end());
    for (string &s: S)
        reverse(s.begin(), s.end());
    for (string &s: Y)
        reverse(s.begin(), s.end());
    int l = 0, r = -1;
    for (query &q: Q)
    {
        if (q.l > q.r)
            continue;
        while (l > q.l)
            add(S[--l]);
        while (r < q.r)
            add(S[++r]);
        while (l < q.l)
            rmv(S[l++]);
        while (r > q.r)
            rmv(S[r--]);
        q.res = cntpref(Y[q.idx]);
    }
    sort(Q.begin(), Q.end(), [](query &p, query &q){return p.idx < q.idx;});
    for (query &q: Q)
        cout<<q.res<<"\n";
}

int main()
{
    if (fopen(_F".INP", "r"))
    {
        freopen(_F".INP", "r", stdin);
        //freopen(_F".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Test = 1; //cin>>Test;
    while (Test--) solve();
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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