Submission #866738

#	Time	Username	Problem	Language	Result	Execution time	Memory
866738		VN_AnhTuan	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	91 ms	73152 KiB

selling_rna

//  Author : Nguyen Anh Tuan - THPT Chuyen Bac Giang - Train VOI 2023/2024

#include<bits/stdc++.h>
#define file(NAME) {freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout);}
#define foru(i, a, b) for(int i=(a);i<=(b);i++)
#define ford(i, a, b) for(int i=(a);i>=(b);i--)
#define fore(x, v) for(auto &x : v)
#define rep(i, n) for(int i=(1);i<=(n);i++)
#define fi first
#define se second
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define RR(X) X.resize(unique(all(X)) - begin(X))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;

namespace IO
{
    #define getchar() (ipos==iend and (iend=(ipos=_ibuf)+fread(_ibuf,1,__bufsize,stdin),ipos==iend)?EOF:*ipos++)
    #define putchar(ch) (opos==oend?fwrite(_obuf,1,__bufsize,stdout),opos=_obuf:0,*opos++=(ch))
    #define __bufsize (1<<20)
    char _ibuf[__bufsize],_obuf[__bufsize],_stk[20];
    char *ipos=_ibuf,*iend=_ibuf,*opos=_obuf,*oend = _obuf+__bufsize,*stkpos = _stk;
    struct END{~END(){fwrite(_obuf,1,opos-_obuf,stdout);}}__;
    inline void read(int &x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
    inline void lread(ll&x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void lwrite(ll x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
};

void maximum(ll &a, ll b) {if(b > a) a = b;}
void minimum(ll &a, ll b) {if(b < a) a = b;}
bool bit(int x, int i) {return (x >> i) & 1;}

//-----------------------------------------------------------------------------------
//      END OF TEMPLATE
//-----------------------------------------------------------------------------------
//      Nguyen Anh Tuan - AnhTuan_BG
//      PRAY FOR VOI 2023
//-----------------------------------------------------------------------------------

const int maxn = 1e5 + 5;

int n, m, ans[maxn];
string s[maxn], q[maxn];
vector<int> v[maxn];

int id[300];

void prep()
{
    id['A'] = 0;
    id['G'] = 1;
    id['C'] = 2;
    id['U'] = 3;
}

struct node
{
    int child[4];
    int mn = maxn, mx = -maxn, cnt = 0;
    node()
    {
         memset(child, -1, sizeof(child));
    }
};
vector<node> trie(1);

void add(string s, int idx)
{
    int Time = 0, n = s.size();
    for(char c : s)
    {
        int ch = id[c];
        if (trie[Time].child[ch] == -1)
        {
            trie[Time].child[ch] = sz(trie);
            trie.push_back(node());
        }
        Time = trie[Time].child[ch];
        trie[Time].cnt += 1;
        trie[Time].mn = min(trie[Time].mn, idx);
        trie[Time].mx = max(trie[Time].mx, idx);
    }
}

int get(string s)
{
    int Time = 0;
    for(char c : s)
    {
        int ch = id[c];
        if(trie[Time].child[ch] == -1) return -1;
        Time = trie[Time].child[ch];
    }
    return Time;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //file("");

    prep();
    cin >> n >> m;

    foru(i, 1, n) cin >> s[i];
    sort(s + 1, s + n + 1);
    foru(i, 1, n) add(s[i], i);

    foru(i, 1, m)
    {
        string p;
        cin >> p >> q[i];
        reverse(all(q[i]));
        int tmp = get(p);
        if (tmp != -1)
        {
            int l = trie[tmp].mn, r = trie[tmp].mx;
            v[l - 1].push_back(-i);
            v[r].push_back(i);
        }
    }

    trie.clear();
    trie.push_back(node());

    foru(i, 1, n)
    {
        reverse(all(s[i]));
        add(s[i], i);

        fore(j, v[i])
        {
            if (j < 0)
            {
                int tmp = get(q[-j]);
                if (tmp != -1) ans[-j] -= trie[tmp].cnt;
            }
            else
            {
                int tmp = get(q[j]);
                if (tmp != -1) ans[j] += trie[tmp].cnt;
            }
        }
    }

    foru(i, 1, m) cout << ans[i] << "\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:101:21: warning: array subscript has type 'char' [-Wchar-subscripts]
  101 |         int ch = id[c];
      |                     ^
selling_rna.cpp:98:19: warning: unused variable 'n' [-Wunused-variable]
   98 |     int Time = 0, n = s.size();
      |                   ^
selling_rna.cpp: In function 'int get(std::string)':
selling_rna.cpp:119:21: warning: array subscript has type 'char' [-Wchar-subscripts]
  119 |         int ch = id[c];
      |                     ^

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