oj.uz

Submission #858973

# Submission time Handle Problem Language Result Execution time Memory
858973 2023-10-09T13:47:55 Z hungt58 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 262 ms 415364 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=1e6+10;
ll n,m,tim[3];
string s[maxn];
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 11 ms 56408 KB Output is correct
2 Correct 11 ms 56280 KB Output is correct
3 Correct 11 ms 56408 KB Output is correct
4 Correct 11 ms 56412 KB Output is correct
5 Correct 12 ms 56412 KB Output is correct
6 Correct 12 ms 56156 KB Output is correct
7 Correct 11 ms 56412 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 415364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 57912 KB Output is correct
2 Correct 27 ms 58200 KB Output is correct
3 Correct 32 ms 57956 KB Output is correct
4 Correct 25 ms 57444 KB Output is correct
5 Correct 28 ms 57956 KB Output is correct
6 Correct 33 ms 57944 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56408 KB Output is correct
2 Correct 11 ms 56280 KB Output is correct
3 Correct 11 ms 56408 KB Output is correct
4 Correct 11 ms 56412 KB Output is correct
5 Correct 12 ms 56412 KB Output is correct
6 Correct 12 ms 56156 KB Output is correct
7 Correct 11 ms 56412 KB Output is correct
8 Runtime error 262 ms 415364 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -