oj.uz

Submission #488360

# Submission time Handle Problem Language Result Execution time Memory
488360 2021-11-18T17:51:04 Z alexx_stefan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 280 ms 201696 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 163996 KB Output is correct
2 Correct 204 ms 155976 KB Output is correct
3 Correct 215 ms 162204 KB Output is correct
4 Correct 212 ms 154776 KB Output is correct
5 Correct 246 ms 198808 KB Output is correct
6 Correct 280 ms 201696 KB Output is correct
7 Correct 74 ms 11460 KB Output is correct
8 Correct 202 ms 123512 KB Output is correct
9 Correct 195 ms 105512 KB Output is correct
10 Correct 174 ms 100304 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12712 KB Output is correct
2 Correct 24 ms 10380 KB Output is correct
3 Correct 24 ms 11340 KB Output is correct
4 Correct 19 ms 10344 KB Output is correct
5 Correct 21 ms 10664 KB Output is correct
6 Correct 26 ms 12080 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 220 ms 163996 KB Output is correct
9 Correct 204 ms 155976 KB Output is correct
10 Correct 215 ms 162204 KB Output is correct
11 Correct 212 ms 154776 KB Output is correct
12 Correct 246 ms 198808 KB Output is correct
13 Correct 280 ms 201696 KB Output is correct
14 Correct 74 ms 11460 KB Output is correct
15 Correct 202 ms 123512 KB Output is correct
16 Correct 195 ms 105512 KB Output is correct
17 Correct 174 ms 100304 KB Output is correct
18 Correct 36 ms 12712 KB Output is correct
19 Correct 24 ms 10380 KB Output is correct
20 Correct 24 ms 11340 KB Output is correct
21 Correct 19 ms 10344 KB Output is correct
22 Correct 21 ms 10664 KB Output is correct
23 Correct 26 ms 12080 KB Output is correct
24 Correct 225 ms 137500 KB Output is correct
25 Correct 235 ms 140704 KB Output is correct
26 Correct 200 ms 135104 KB Output is correct
27 Correct 209 ms 136488 KB Output is correct
28 Correct 142 ms 41980 KB Output is correct
29 Correct 104 ms 22464 KB Output is correct