oj.uz

Submission #624347

# Submission time Handle Problem Language Result Execution time Memory
624347 2022-08-08T02:30:44 Z duypd4206 Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 216 ms 49996 KB 
#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define pb push_back
#define all(x) (x.begin(), x.end())
typedef pair<int,int> ii;
using ll = long long ;

const int maxn = 1e5 + 1;
const int oo = 1e9 + 7;
const ll ooo = 2e18 + 7;
const int mod = 1e9 + 7;

struct node
{
    int nxt[4] ;
    node()
    {
        memset(nxt, -1, sizeof(nxt));
    }
    vector<int> id;
};
int aa(char c)
{
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    if(c == 'U') return 3;
}
node tmp;
struct Trie
{
    vector<node> trie;
    Trie() {trie.emplace_back(tmp);}
    void add(string s, int id)
    {
        int i = 0;
        for(auto c : s)
        {
            int ii = aa(c);
            if(trie[i].nxt[ii] == -1)
            {
                trie[i].nxt[ii] = trie.size();
                trie.emplace_back(tmp);
            }
            trie[i].id.pb(id);
            i = trie[i].nxt[ii];
        }
        trie[i].id.pb(id);
    }

    int get(string s)
    {
        int i = 0;
        for(auto c :s)
        {
            int ii = aa(c);
            if(trie[i].nxt[ii] == -1)
                return -1;
            i = trie[i].nxt[ii];
        }
        return i;
    }

};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
#define file ""
    freopen(file"inp","r",stdin);
    freopen(file"out","w",stdout);
#endif //ONLINE_JUDGE
    int n, m;
    cin >> n >> m;
    Trie trie, rtrie;
    string s;
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        trie.add(s, i);
        reverse(s.begin(), s.end());
        rtrie.add(s, i);
    }
    string p, q;
    for(int i = 1; i <= m; i++)
    {
        cin >> p >> q;
        reverse(q.begin(), q.end());
        int sp = trie.get(p), sq = rtrie.get(q);
        if(sp == -1 || sq == -1)
        {
            cout << 0 << "\n";
            continue;
        }
        vector<int> vp = trie.trie[sp].id;
        vector<int> vq = rtrie.trie[sq].id;
        int l = vp.front(), r = vp.back();
        int ll = lower_bound(vq.begin(), vq.end(), l) - vq.begin();
        int rr = upper_bound(vq.begin(), vq.end(), r) - vq.begin();
        if(ll == vq.size() || ll > rr)
            cout << 0 << "\n";
        else cout << rr - ll << "\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:104:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if(ll == vq.size() || ll > rr)
      |            ~~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int aa(char)':
selling_rna.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
   31 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen(file"inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen(file"out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 49816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 49996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 49812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 49816 KB Output isn't correct
2 Halted 0 ms 0 KB -