oj.uz

Submission #866738

# Submission time Handle Problem Language Result Execution time Memory
866738 2023-10-27T01:46:20 Z VN_AnhTuan Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 91 ms 73152 KB 
//  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

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 71664 KB Output is correct
2 Correct 59 ms 70612 KB Output is correct
3 Correct 65 ms 72180 KB Output is correct
4 Correct 68 ms 71900 KB Output is correct
5 Correct 48 ms 71108 KB Output is correct
6 Correct 48 ms 70028 KB Output is correct
7 Correct 43 ms 14552 KB Output is correct
8 Correct 74 ms 43044 KB Output is correct
9 Correct 63 ms 42584 KB Output is correct
10 Correct 45 ms 42192 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11760 KB Output is correct
2 Correct 15 ms 11612 KB Output is correct
3 Correct 18 ms 11612 KB Output is correct
4 Correct 14 ms 11356 KB Output is correct
5 Correct 16 ms 11456 KB Output is correct
6 Correct 19 ms 11628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10688 KB Output is correct
8 Correct 56 ms 71664 KB Output is correct
9 Correct 59 ms 70612 KB Output is correct
10 Correct 65 ms 72180 KB Output is correct
11 Correct 68 ms 71900 KB Output is correct
12 Correct 48 ms 71108 KB Output is correct
13 Correct 48 ms 70028 KB Output is correct
14 Correct 43 ms 14552 KB Output is correct
15 Correct 74 ms 43044 KB Output is correct
16 Correct 63 ms 42584 KB Output is correct
17 Correct 45 ms 42192 KB Output is correct
18 Correct 19 ms 11760 KB Output is correct
19 Correct 15 ms 11612 KB Output is correct
20 Correct 18 ms 11612 KB Output is correct
21 Correct 14 ms 11356 KB Output is correct
22 Correct 16 ms 11456 KB Output is correct
23 Correct 19 ms 11628 KB Output is correct
24 Correct 71 ms 72244 KB Output is correct
25 Correct 71 ms 73152 KB Output is correct
26 Correct 64 ms 70856 KB Output is correct
27 Correct 70 ms 71864 KB Output is correct
28 Correct 91 ms 23804 KB Output is correct
29 Correct 67 ms 12440 KB Output is correct