oj.uz

Submission #1070506

# Submission time Handle Problem Language Result Execution time Memory
1070506 2024-08-22T14:50:13 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 112 ms 60244 KB 
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
using lli = long long;
const int maxN = 1e5 + 5;
const int maxS = 4e6 + 5;
const int maxA = 4;
int tr[maxS][maxA],cnt,h[maxS];
string q[maxN],s[maxN],p[maxN],s1[maxN];
int n,m,idn[maxN],idm[maxN],res[maxN];
int tk(char c)
{
    if (c == 'G') return 0;
    if (c == 'U') return 1;
    if (c == 'C') return 2;
    if (c == 'A') return 3;
}
void add(string s)
{
    int node = 0;
    for (char c : s)
    {
        if (tr[node][tk(c)] == 0) tr[node][tk(c)] = ++cnt;
        node = tr[node][tk(c)];
        h[node]++;
    }
}
void del(const string& s)
{
    int node = 0;
    for (char c : s)
    {
        int pos = node;
        node = tr[node][tk(c)];
        h[node]--;
    }
}
int calc(const string& s)
{
    int node = 0;
    for (char c : s)
    {
        if (tr[node][tk(c)] == 0) return 0;
        node = tr[node][tk(c)];
    }
    return h[node];
}
bool cmp(const int& a,const int& b)
{
    return s[a] < s[b];
}
bool cmp1(const int& a,const int& b)
{
    return p[a] < p[b];
}
void input()
{
    cnt = 0;
    cin >> n >> m;
    for (int i = 1;i <= n;++i)
    {
        cin >> s[i];
        idn[i] = i;
    }
    for (int i = 1;i <= m;++i)
    {
        idm[i] = i;
        cin >> p[i] >> q[i];
        reverse(q[i].begin(),q[i].end());
    }
    sort(idn + 1,idn + n + 1,cmp);
    sort(idm + 1,idm + m + 1,cmp1);
}
bool check(const string& b,const string& a)
{
    if (a.size() > b.size()) return false;
    for (int i = 0;i < a.size();++i)
        if (a[i] != b[i]) return false;
    return true;
}
void solve()
{
    for (int i = 1;i <= n;++i)
    {
        reverse(s[i].begin(),s[i].end());
        s1[i] = s[i];
        reverse(s[i].begin(),s[i].end());
    }
    int l = 1,r = 0;
    for (int i = 1;i <= m;++i)
    {
        while (l <= n && p[idm[i]] > s[idn[l]] && !check(s[idn[l]],p[idm[i]]))
        {
            if (l <= r) del(s1[idn[l]]);
            ++l;
        }
        r = max(l - 1,r);
        while (r + 1 <= n && check(s[idn[r + 1]],p[idm[i]]))
        {
            ++r;
            add(s1[idn[r]]);
        }
        while (r >= l && !check(s[idn[r]],p[idm[i]]))
        {
            del(s1[idn[r]]);
            --r;
        }
        res[idm[i]] = calc(q[idm[i]]);
    }
    for (int i = 1;i <= m;++i) cout << res[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("D.inp","r",stdin);
//    freopen("D.out","w",stdout);
    input();
    solve();
}

Compilation message

selling_rna.cpp: In function 'void del(const string&)':
selling_rna.cpp:34:13: warning: unused variable 'pos' [-Wunused-variable]
   34 |         int pos = node;
      |             ^~~
selling_rna.cpp: In function 'bool check(const string&, const string&)':
selling_rna.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0;i < a.size();++i)
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int tk(char)':
selling_rna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 60244 KB Output is correct
2 Correct 41 ms 58716 KB Output is correct
3 Correct 43 ms 22872 KB Output is correct
4 Correct 43 ms 23092 KB Output is correct
5 Correct 63 ms 42324 KB Output is correct
6 Correct 65 ms 45136 KB Output is correct
7 Correct 34 ms 29488 KB Output is correct
8 Correct 40 ms 38648 KB Output is correct
9 Correct 41 ms 38356 KB Output is correct
10 Correct 27 ms 35468 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17244 KB Output is correct
2 Correct 16 ms 16988 KB Output is correct
3 Correct 20 ms 16988 KB Output is correct
4 Correct 16 ms 16988 KB Output is correct
5 Correct 18 ms 16988 KB Output is correct
6 Correct 23 ms 17132 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16880 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 38 ms 60244 KB Output is correct
9 Correct 41 ms 58716 KB Output is correct
10 Correct 43 ms 22872 KB Output is correct
11 Correct 43 ms 23092 KB Output is correct
12 Correct 63 ms 42324 KB Output is correct
13 Correct 65 ms 45136 KB Output is correct
14 Correct 34 ms 29488 KB Output is correct
15 Correct 40 ms 38648 KB Output is correct
16 Correct 41 ms 38356 KB Output is correct
17 Correct 27 ms 35468 KB Output is correct
18 Correct 22 ms 17244 KB Output is correct
19 Correct 16 ms 16988 KB Output is correct
20 Correct 20 ms 16988 KB Output is correct
21 Correct 16 ms 16988 KB Output is correct
22 Correct 18 ms 16988 KB Output is correct
23 Correct 23 ms 17132 KB Output is correct
24 Correct 54 ms 57040 KB Output is correct
25 Correct 54 ms 57680 KB Output is correct
26 Correct 50 ms 56352 KB Output is correct
27 Correct 57 ms 27420 KB Output is correct
28 Correct 112 ms 31196 KB Output is correct
29 Correct 66 ms 20560 KB Output is correct