oj.uz

Submission #866739

# Submission time Handle Problem Language Result Execution time Memory
866739 2023-10-27T01:48:28 Z VN_AnhTuan Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 89 ms 73192 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];

struct node
{
    int child[4];
    int minn = maxn, maxx = -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].minn = min(trie[Time].minn, idx);
        trie[Time].maxx = max(trie[Time].maxx, 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("");

    id['A'] = 0;
    id['G'] = 1;
    id['C'] = 2;
    id['U'] = 3;
    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].minn, r = trie[tmp].maxx;
            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";

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 71636 KB Output is correct
2 Correct 59 ms 70616 KB Output is correct
3 Correct 70 ms 70820 KB Output is correct
4 Correct 73 ms 71592 KB Output is correct
5 Correct 48 ms 70324 KB Output is correct
6 Correct 49 ms 71608 KB Output is correct
7 Correct 43 ms 14536 KB Output is correct
8 Correct 67 ms 43716 KB Output is correct
9 Correct 73 ms 41864 KB Output is correct
10 Correct 46 ms 43508 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11752 KB Output is correct
2 Correct 15 ms 11608 KB Output is correct
3 Correct 18 ms 11608 KB Output is correct
4 Correct 14 ms 11356 KB Output is correct
5 Correct 15 ms 11356 KB Output is correct
6 Correct 22 ms 11668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10684 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 57 ms 71636 KB Output is correct
9 Correct 59 ms 70616 KB Output is correct
10 Correct 70 ms 70820 KB Output is correct
11 Correct 73 ms 71592 KB Output is correct
12 Correct 48 ms 70324 KB Output is correct
13 Correct 49 ms 71608 KB Output is correct
14 Correct 43 ms 14536 KB Output is correct
15 Correct 67 ms 43716 KB Output is correct
16 Correct 73 ms 41864 KB Output is correct
17 Correct 46 ms 43508 KB Output is correct
18 Correct 19 ms 11752 KB Output is correct
19 Correct 15 ms 11608 KB Output is correct
20 Correct 18 ms 11608 KB Output is correct
21 Correct 14 ms 11356 KB Output is correct
22 Correct 15 ms 11356 KB Output is correct
23 Correct 22 ms 11668 KB Output is correct
24 Correct 68 ms 70800 KB Output is correct
25 Correct 75 ms 73192 KB Output is correct
26 Correct 72 ms 71176 KB Output is correct
27 Correct 69 ms 70844 KB Output is correct
28 Correct 89 ms 22788 KB Output is correct
29 Correct 55 ms 12368 KB Output is correct