oj.uz

Submission #866735

# Submission time Handle Problem Language Result Execution time Memory
866735 2023-10-27T01:11:28 Z tradz Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 222 ms 444392 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll int
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<ll,ll> ii;
const ll maxn=5e6+10;
ll n,m,tim[3];
string s[100010];
struct di
{
    ll child[27],in,ou;
};
vector<ll> c[maxn];
di a[maxn],b[maxn];
void update(ll w)
{
    string sa=s[w];
    ll u=0;
    for (ll i=0;i<sa.size();i++)
    {
    if (a[u].child[sa[i]-'A'+1]==0)
    {

        a[u].child[sa[i]-'A'+1]=++tim[1];
        a[tim[1]].in=w;
    }
    u=a[u].child[sa[i]-'A'+1];
    a[u].ou=w;

    }
    u=0;
    for (ll i=sa.size()-1;i>=0;i--)
    {
    if (b[u].child[sa[i]-'A'+1]==0)
    {
        b[u].child[sa[i]-'A'+1]=++tim[2];
    }
    u=b[u].child[sa[i]-'A'+1];

    c[u].push_back(w);

    }
}
void get (string sa,string sb)
{
    ll u=0,ua=0;
    for (ll i=0;i<sa.size();i++)
    if (a[u].child[sa[i]-'A'+1]!=0) u=a[u].child[sa[i]-'A'+1]; else {cout<<"0";return;}

    for (ll i=sb.size()-1;i>=0;i--)
    if (b[ua].child[sb[i]-'A'+1]!=0) ua=b[ua].child[sb[i]-'A'+1]; else {cout<<"0";return;}
    c[ua].push_back(1000000);
    ll w=lower_bound(c[ua].begin(),c[ua].end(),a[u].in)-c[ua].begin();
    ll wa=upper_bound(c[ua].begin(),c[ua].end(),a[u].ou)-c[ua].begin();
    wa--;

    if (w>wa) {cout<<"0";return;}
    cout<<wa-w+1;
}
int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (ll i=1;i<=n;i++)
    cin>>s[i];
    sort (s+1,s+n+1);
    for (ll i=1;i<=n;i++) update(i);
    for (ll i=1;i<=m;i++)
    {
        cin>>s[1]>>s[2];
        get (s[1],s[2]);
        cout<<'\n';
    }


}

Compilation message

selling_rna.cpp: In function 'void update(int)':
selling_rna.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (ll i=0;i<sa.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp: In function 'void get(std::string, std::string)':
selling_rna.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (ll i=0;i<sa.size();i++)
      |                 ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 120920 KB Output is correct
2 Correct 27 ms 121176 KB Output is correct
3 Correct 26 ms 121100 KB Output is correct
4 Correct 27 ms 120924 KB Output is correct
5 Correct 26 ms 120924 KB Output is correct
6 Correct 26 ms 120924 KB Output is correct
7 Correct 26 ms 120924 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 412560 KB Output is correct
2 Correct 219 ms 397084 KB Output is correct
3 Correct 103 ms 360004 KB Output is correct
4 Correct 107 ms 349264 KB Output is correct
5 Correct 184 ms 439556 KB Output is correct
6 Correct 184 ms 444392 KB Output is correct
7 Correct 68 ms 136772 KB Output is correct
8 Correct 197 ms 320984 KB Output is correct
9 Correct 166 ms 290388 KB Output is correct
10 Correct 126 ms 282180 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 122744 KB Output is correct
2 Correct 41 ms 122960 KB Output is correct
3 Correct 45 ms 122668 KB Output is correct
4 Correct 39 ms 122200 KB Output is correct
5 Correct 42 ms 122704 KB Output is correct
6 Correct 50 ms 122708 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 120920 KB Output is correct
2 Correct 27 ms 121176 KB Output is correct
3 Correct 26 ms 121100 KB Output is correct
4 Correct 27 ms 120924 KB Output is correct
5 Correct 26 ms 120924 KB Output is correct
6 Correct 26 ms 120924 KB Output is correct
7 Correct 26 ms 120924 KB Output is correct
8 Correct 220 ms 412560 KB Output is correct
9 Correct 219 ms 397084 KB Output is correct
10 Correct 103 ms 360004 KB Output is correct
11 Correct 107 ms 349264 KB Output is correct
12 Correct 184 ms 439556 KB Output is correct
13 Correct 184 ms 444392 KB Output is correct
14 Correct 68 ms 136772 KB Output is correct
15 Correct 197 ms 320984 KB Output is correct
16 Correct 166 ms 290388 KB Output is correct
17 Correct 126 ms 282180 KB Output is correct
18 Correct 50 ms 122744 KB Output is correct
19 Correct 41 ms 122960 KB Output is correct
20 Correct 45 ms 122668 KB Output is correct
21 Correct 39 ms 122200 KB Output is correct
22 Correct 42 ms 122704 KB Output is correct
23 Correct 50 ms 122708 KB Output is correct
24 Correct 222 ms 360216 KB Output is correct
25 Correct 221 ms 360632 KB Output is correct
26 Correct 214 ms 357204 KB Output is correct
27 Correct 101 ms 318352 KB Output is correct
28 Correct 157 ms 167500 KB Output is correct
29 Correct 85 ms 130036 KB Output is correct