Submission #971281

#	Time	Username	Problem	Language	Result	Execution time	Memory
971281		12345678	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	194 ms	209492 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, q, mp[100], v[nx], t, res[nx];
string s[nx], st, qrs[nx];
vector<int> d[nx], rem[nx];

struct node
{
    int mn=1e9, mx=-1e9, sz=0;
    vector<int> ed;
    node* p[4]={0, 0, 0, 0};
};
typedef node* pnode;

pnode rt=new node(), rv=new node();

void add(pnode &k, int i, int idx, int sz)
{
    if (idx==sz) k->ed.push_back(i);
    else
    {
        if (!(k->p[mp[s[i][idx]]])) k->p[mp[s[i][idx]]]=new node();
        add(k->p[mp[s[i][idx]]], i, idx+1, sz);
    }
    k->sz=k->ed.size();
    for (int i=0; i<4; i++) if (k->p[i]) k->sz+=k->p[i]->sz;
}

void dfs(pnode k)
{
    for (auto x:k->ed) v[++t]=x, k->mn=min(k->mn, t), k->mx=max(k->mx, t);
    for (int i=0; i<4; i++) if (k->p[i]) dfs(k->p[i]), k->mn=min(k->mn, k->p[i]->mn), k->mx=max(k->mx, k->p[i]->mx);
}

pair<int, int> query(pnode k, int idx, int sz)
{
    if (idx==sz) return {k->mn, k->mx};
    if (!(k->p[mp[st[idx]]])) return {-1, -1};
    return query(k->p[mp[st[idx]]], idx+1, sz);
}

int querysz(pnode k, int idx, int sz)
{
    if (idx==sz) return k->sz;
    if (!(k->p[mp[st[idx]]])) return 0;
    return querysz(k->p[mp[st[idx]]], idx+1, sz);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    mp['A']=0; mp['G']=1; mp['C']=2; mp['U']=3;
    for (int i=1; i<=n; i++) cin>>s[i], add(rt, i, 0, s[i].size());
    dfs(rt);
    for (int i=1; i<=q; i++)
    {
        cin>>st>>qrs[i];
        reverse(qrs[i].begin(), qrs[i].end());
        auto x=query(rt, 0, st.size());
        if (x.first==-1) continue;
        rem[x.first].push_back(i);
        d[x.second].push_back(i);
        //cout<<"query "<<i<<' '<<x.first<<' '<<x.second<<'\n';
    }
    for (int i=1; i<=n; i++) reverse(s[i].begin(), s[i].end());
    //for (int i=1; i<=n; i++) cout<<"order "<<i<<' '<<v[i]<<'\n';
    for (int i=1; i<=n; i++) 
    {
        int idx=v[i];
        for (auto x:rem[i]) st=qrs[x], res[x]-=querysz(rv, 0, st.size());
        add(rv, idx, 0, s[idx].size());
        for (auto x:d[i]) st=qrs[x], res[x]+=querysz(rv, 0, st.size());
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(node*&, int, int, int)':
selling_rna.cpp:26:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         if (!(k->p[mp[s[i][idx]]])) k->p[mp[s[i][idx]]]=new node();
      |                                ^
selling_rna.cpp:26:54: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         if (!(k->p[mp[s[i][idx]]])) k->p[mp[s[i][idx]]]=new node();
      |                                                      ^
selling_rna.cpp:27:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         add(k->p[mp[s[i][idx]]], i, idx+1, sz);
      |                              ^
selling_rna.cpp: In function 'std::pair<int, int> query(pnode, int, int)':
selling_rna.cpp:42:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |     if (!(k->p[mp[st[idx]]])) return {-1, -1};
      |                          ^
selling_rna.cpp:43:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |     return query(k->p[mp[st[idx]]], idx+1, sz);
      |                                 ^
selling_rna.cpp: In function 'int querysz(pnode, int, int)':
selling_rna.cpp:49:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if (!(k->p[mp[st[idx]]])) return 0;
      |                          ^
selling_rna.cpp:50:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |     return querysz(k->p[mp[st[idx]]], idx+1, sz);
      |                                   ^

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