oj.uz

답안 #1070636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070636 2024-08-22T16:18:45 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 278 ms 533328 KB 
//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(cur->v[l],cur->v[k]) >= x.size()) k1 = l;
                    else k1 = r;
                    break;
                }
                ll mid = (l + r) / 2;
                if(get(cur->v[mid],cur->v[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

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: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]
  104 |                     if(get(cur->v[l],cur->v[k]) >= x.size()) k1 = l;
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:109: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]
  109 |                 if(get(cur->v[mid],cur->v[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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 533328 KB Output is correct
2 Correct 278 ms 505424 KB Output is correct
3 Correct 54 ms 37228 KB Output is correct
4 Correct 54 ms 36692 KB Output is correct
5 Correct 228 ms 336428 KB Output is correct
6 Correct 256 ms 341328 KB Output is correct
7 Correct 44 ms 31572 KB Output is correct
8 Correct 158 ms 217512 KB Output is correct
9 Correct 132 ms 188752 KB Output is correct
10 Correct 112 ms 179412 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 20280 KB Output is correct
2 Correct 24 ms 17244 KB Output is correct
3 Correct 30 ms 19104 KB Output is correct
4 Correct 20 ms 16340 KB Output is correct
5 Correct 29 ms 16624 KB Output is correct
6 Correct 34 ms 18644 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 252 ms 533328 KB Output is correct
9 Correct 278 ms 505424 KB Output is correct
10 Correct 54 ms 37228 KB Output is correct
11 Correct 54 ms 36692 KB Output is correct
12 Correct 228 ms 336428 KB Output is correct
13 Correct 256 ms 341328 KB Output is correct
14 Correct 44 ms 31572 KB Output is correct
15 Correct 158 ms 217512 KB Output is correct
16 Correct 132 ms 188752 KB Output is correct
17 Correct 112 ms 179412 KB Output is correct
18 Correct 30 ms 20280 KB Output is correct
19 Correct 24 ms 17244 KB Output is correct
20 Correct 30 ms 19104 KB Output is correct
21 Correct 20 ms 16340 KB Output is correct
22 Correct 29 ms 16624 KB Output is correct
23 Correct 34 ms 18644 KB Output is correct
24 Correct 255 ms 443980 KB Output is correct
25 Correct 276 ms 443936 KB Output is correct
26 Correct 247 ms 438864 KB Output is correct
27 Correct 69 ms 38484 KB Output is correct
28 Correct 220 ms 110908 KB Output is correct
29 Correct 82 ms 44092 KB Output is correct