Submission #488360

#	Time	Username	Problem	Language	Result	Execution time	Memory
488360		alexx_stefan	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	280 ms	201696 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define dim 200006
#define mod 666013//1000000007
using namespace std;
ifstream fin ("trie.in");
ofstream fout("trie.out");
string s;
int n,indice,v[dim],unu[dim],ans[dim],trans[300];
vector<int>lin[3];

struct trie
{
    int st,dr;
    vector<int> id;
    trie *kids[4];
    trie ()
    {
        for (int i=0; i<=3; i++)
            kids[i]=nullptr;
    }
};

trie* insert (trie *node,int index)
{
    if (node==nullptr)
        node=new trie;
    if (index==(int)s.size())
    {
        node->id.push_back(indice);
        return node;
    }
    node->kids[trans[s[index]]]=insert(node->kids[trans[s[index]]],index+1);
    return node;
}

string intoarce (string s)
{
    int i=0,j=s.size()-1;
    for (; i<j; i++,j--)
        swap(s[i],s[j]);
    return s;
}

trie *dfs (trie *node)
{
    if (node==nullptr)
        return nullptr;
    node->st=(int)lin[indice].size();
    for (auto x:node->id)
        lin[indice].push_back(x);
    for (int i=0; i<4; i++)
        node->kids[i]=dfs(node->kids[i]);
    node->dr=(int)lin[indice].size()-1;
    return node;
}

pair<int,int> get (trie *node,int index)
{
    if (node==nullptr)
        return {-1,-1};
    if (index==(int)s.size())
        return {node->st,node->dr};
    else    return get(node->kids[trans[s[index]]],index+1);
}

struct element
{
    int l,r,index,coef;
};
vector<element> query[dim];

void update (int poz, int val)
{
    for (int i=poz; i<=n; i=i+(i&-i))
        v[i]=v[i]+val;
}

int ask (int poz)
{
    int sum=0;
    for (int i=poz; i>=1; i=i-(i&-i))
        sum+=v[i];
    return sum;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    trans['G']=1,trans['C']=2,trans['U']=3;
    int t,i;
    trie *pr=nullptr;
    trie *sf=nullptr;
    cin>>n>>t;
    cin.get();
    for (i=1; i<=n; i++)
    {
        cin>>s;
        indice=i;
        pr=insert(pr,0);
        s=intoarce(s);
        sf=insert(sf,0);
    }
    lin[1].push_back(0);
    lin[2].push_back(0);
    indice=1;
    pr=dfs(pr);
    indice=2;
    sf=dfs(sf);
    for (i=1; i<=t; i++)
    {
        cin>>s;
        pair<int,int>el1=get(pr,0);
        cin>>s;
        s=intoarce(s);
        pair<int,int>el2=get(sf,0);
        if (el1.first!=-1&&el2.first!=-1)
        {
        query[el2.first-1].push_back({el1.first,el1.second,i,-1});
        query[el2.second].push_back({el1.first,el1.second,i,1});
        }
    }
    for (i=1; i<=n; i++)
        unu[lin[1][i]]=i;
    for (i=1; i<=n; i++)
    {
        update(unu[lin[2][i]],1);
        for (element q:query[i])
        ans[q.index]+=q.coef*(ask(q.r)-ask(q.l-1));
    }
    for (i=1; i<=t; i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'trie* insert(trie*, long long int)':
selling_rna.cpp:33:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |     node->kids[trans[s[index]]]=insert(node->kids[trans[s[index]]],index+1);
      |                              ^
selling_rna.cpp:33:65: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |     node->kids[trans[s[index]]]=insert(node->kids[trans[s[index]]],index+1);
      |                                                                 ^
selling_rna.cpp: In function 'std::pair<long long int, long long int> get(trie*, long long int)':
selling_rna.cpp:64:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |     else    return get(node->kids[trans[s[index]]],index+1);
      |                                                 ^

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