Submission #1279931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279931		han^	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	16 ms	31768 KiB

selling_rna

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define N 1000005
using namespace std;

int n, q;
string s[N];

int stranform(char x)
{
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    return 3;
}

struct Trie
{
    struct Node
    {
        Node* c[4];
        int l, r;
        Node()
        {
            For (i, 0, 3) c[i] = 0;
            l = 2e9;
            r = 0;
        }
    };
    Node* root;
    Trie()
    {
        root = new Node();
    }
    void add (string s, int id)
    {
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                p->c[x] = new Node();
            p = p->c[x];
            if (id < p->l) p->l = id;
            if (id > p->r) p->r = id;
        }
    }
    ii get (string s)
    {
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform(s[i]);
            if (!p->c[x])
                return {2e9, 2e9};
            p = p->c[x];
        }
        return {p->l, p->r};
    }
};

struct RTrie
{
    struct Node
    {
        Node* c[4];
        vector<int> id;
        Node()
        {
            For (i, 0, 3) c[i] = 0;
        }
    };
    Node* root;
    RTrie()
    {
        root = new Node();
    }
    void add (string s, int id)
    {
        reverse (s.begin(), s.end() );
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                p->c[x] = new Node();
            p = p->c[x];
            p->id.push_back (id);
        }
    }
    int get (string s, ii k)
    {
        int l = k.fi, r = k.se;
        if (l == r && l == 2e9)
            return 0;
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                return 0;
            p = p->c[x];
        }
        return upper_bound (p->id.begin(), p->id.end(), r) - lower_bound (p->id.begin(), p->id.end(), l);
    }
};

int main()
{
    ios_base::sync_with_stdio (0);
    cin.tie (NULL);
    cout.tie (NULL);
    freopen("rna.inp","r",stdin);
    freopen("rna.out","w",stdout);

    cin >> n >> q;
    For (i, 1, n) cin >> s[i];
    sort (s + 1, s + 1 + n);

    Trie t1;
    RTrie t2;
    For (i, 1, n)
    {
        t1.add (s[i], i);
        t2.add (s[i], i);
    }

    while (q--)
    {
        string p, q;
        cin >> p >> q;
        reverse (q.begin(), q.end() );
        cout << t2.get (q, t1.get (p) ) << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:118:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |     freopen("rna.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:119:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     freopen("rna.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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