Submission #1070631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070631		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	302 ms	537076 KiB

selling_rna

//shikanokonokonokokoshitantan

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const ll N = 2e5 + 5;
#define inf LLONG_MAX/2
#define bit(x,y) ((x >> y) & 1)
ll sech[N][30];
ll get(ll l, ll r)
{
    ll cnt = 0;
    ll tmp = 1;
    while(tmp * 2 <= r - l)
    {
        tmp *= 2;
        cnt++;
    }
    return min(sech[l + 1][cnt],sech[r - tmp + 1][cnt]);
}
struct node
{
    node* c[26];
   vector<ll> v;
    node()
    {
        for(ll i = 0;i < 26;i++) c[i] = NULL;
    }
};
string a[N];
struct trie
{
    node root;
    void add(string s, ll t)
    {
        ll i = 0;
        node *cur = &root;
        while(i < s.size())
        {

            ll k = s[i] - 'A';
            if(!cur->c[k])
            {
                cur->c[k] = new node();
            }
            cur = cur->c[k];
            cur->v.push_back(t);
            i++;
        }
    }
    ll cal(string x, string s)
    {
        ll i = 0;
        node *cur = &root;
        ll ans = 0;
        while(i < s.size())
        {
            ll k = s[i] - 'A';
            if(!cur->c[k])
            {
                return 0;
            }
            cur = cur->c[k];
            i++;
        }
        ll l = 0, r = cur->v.size() - 1;
        ll k = 0;
        while(true)
        {
            if(l == r)
            {
                k = l;
                break;
            }
            if(l + 1 == r)
            {
                if(a[cur->v[l]] >= x) k = l;
                else k = r;
                break;
            }
            ll mid = (l + r) / 2;
            if(a[cur->v[mid]] >= x) r = mid;
            else l = mid;
        }
        for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
        if(i >= x.size())
        {
            ll k1;
            l = 0,r = k;
            while(true)
            {
                if(l == r)
                {
                    k1 = l;
                    break;
                }
                if(l + 1 == r)
                {
                    if(get(l,k) >= x.size()) k1 = l;
                    else k1 = r;
                    break;
                }
                ll mid = (l + r) / 2;
                if(get(mid,k) >= x.size()) r = mid;
                else l = mid;
            }
            ll k2;
            l = k,r = cur->v.size() - 1;
            while(true)
            {
                if(l == r)
                {
                    k2 = l;
                    break;
                }
                if(l + 1 == r)
                {
                    if(get(cur->v[k],cur->v[r]) >= x.size()) k2 = r;
                    else k2 = l;
                    break;
                }
                ll mid = (l + r) / 2;
                if(get(cur->v[k],cur->v[mid]) >= x.size()) l = mid;
                else r = mid;
            }
            return k2 - k1 + 1;
        }else return 0;
    }
};
trie f;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q;
    cin >> n >> q;
    ll i,j;
    for(i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1,a + 1 + n);
    for(i = 2;i <= n;i++)
    {
        for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
        {
            if(a[i][j] == a[i - 1][j]) sech[i][0]++;
            else break;
        }
    }
    for(i = 1;i <= 20;i++)
    {
        for(j = 2;j + (1 << (i - 1)) <= n;j++)
        {
            sech[j][i] = min(sech[j][i - 1],sech[j + (1 << (i - 1))][i - 1]);
        }
    }
    for(i = 1;i <= n;i++)
    {
        reverse(a[i].begin(),a[i].end());
        f.add(a[i],i);
        reverse(a[i].begin(),a[i].end());
    }
    while(q--)
    {
        string pre= "";
        string suf= "";
        cin >> pre >> suf;
        reverse(suf.begin(),suf.end());
        cout << f.cal(pre,suf) << "\n";
    }
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie::add(std::string, ll)':
selling_rna.cpp:43:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while(i < s.size())
      |               ~~^~~~~~~~~~
selling_rna.cpp: In member function 'll trie::cal(std::string, std::string)':
selling_rna.cpp:61:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while(i < s.size())
      |               ~~^~~~~~~~~~
selling_rna.cpp:90:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:90:48: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
      |                                              ~~^~~~~~~~~~
selling_rna.cpp:91:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(i >= x.size())
      |            ~~^~~~~~~~~~~
selling_rna.cpp:104:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                     if(get(l,k) >= x.size()) k1 = l;
      |                        ~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:109:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 if(get(mid,k) >= x.size()) r = mid;
      |                    ~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:123:49: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                     if(get(cur->v[k],cur->v[r]) >= x.size()) k2 = r;
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:128:47: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 if(get(cur->v[k],cur->v[mid]) >= x.size()) l = mid;
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:60:12: warning: unused variable 'ans' [-Wunused-variable]
   60 |         ll ans = 0;
      |            ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:148:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
      |                   ~~^~~~~~~~~~~~~
selling_rna.cpp:148:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
      |                                      ~~^~~~~~~~~~~~~~~~~

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