Submission #87295

#	Time	Username	Problem	Language	Result	Execution time	Memory
87295		tieunhi	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	534 ms	258192 KiB

selling_rna

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 100005
#define LN 19

using namespace std;

int n, numQ, Id[N], tt;
string S[N];
string alphabet = "AGCU";
int convertChar(char c) {return alphabet.find(c);}

struct TrieNode
{
    TrieNode *child[4];
    int tin, tout;
    vector<int> all;
    TrieNode()
    {
        FOR(i, 0, 3) child[i] = NULL;
        tin = tout = 0;
        all.resize(0);
    }
};
TrieNode T, T_rev;

void add(string s, int id)
{
    TrieNode *p = &T;
    FOR(i, 0, s.size()-1)
    {
        int c = convertChar(s[i]);
        if (p->child[c] == NULL) p->child[c] = new TrieNode();
        p = p->child[c];
    }
    p->all.PB(id);
}
void add_rev(string s, int id)
{
    TrieNode *p = &T_rev;
    FOR(i, 0, s.size()-1)
    {
        int c = convertChar(s[i]);
        if (p->child[c] == NULL) p->child[c] = new TrieNode();
        p = p->child[c];
        p->all.PB(Id[id]);
    }
}
void DFS(TrieNode *p)
{
    p->tin = ++tt;
    if (p->all.size())
    {
        for (auto x : p->all)
            Id[x] = tt;
    }
    FOR(i, 0, 3)
    {
        if (p->child[i] == NULL) continue;
        DFS(p->child[i]);
    }
    p->tout = tt;
}
void DFS_Rev(TrieNode *p)
{
    sort(p->all.begin(), p->all.end());
    FOR(i, 0, 3)
    {
        if (p->child[i] == NULL) continue;
        DFS_Rev(p->child[i]);
    }
}
pii getRange(string s)
{
    TrieNode *p = &T;
    FOR(i, 0, s.size()-1)
    {
        int c = convertChar(s[i]);
        if (p->child[c] == NULL) return mp(0, 0);
        p = p->child[c];
    }
    return mp(p->tin, p->tout);
}
int getAns(string s, pii Range)
{
    TrieNode *p = &T_rev;
    FOR(i, 0, s.size()-1)
    {
        int c = convertChar(s[i]);
        if (p->child[c] == NULL) return 0;
        p = p->child[c];
    }
    int l = lower_bound(p->all.begin(), p->all.end(), Range.F) - p->all.begin();
    int r = upper_bound(p->all.begin(), p->all.end(), Range.S) - p->all.begin()-1;
    return (r - l + 1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> numQ;
    FOR(i, 1, n) cin >> S[i];
    FOR(i, 1, n) add(S[i], i);
    DFS(&T);
    FOR(i, 1, n) reverse(S[i].begin(), S[i].end());
    FOR(i, 1, n) add_rev(S[i], i);
    DFS_Rev(&T_rev);

    while (numQ--)
    {
        string P, Q; cin >> P >> Q;
        reverse(Q.begin(), Q.end());
        pii R = getRange(P);
        cout <<getAns(Q, R)<<'\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::__cxx11::string, int)':
selling_rna.cpp:7:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, u, v) for (int i = u; i <= v; i++)
selling_rna.cpp:38:9:
     FOR(i, 0, s.size()-1)
         ~~~~~~~~~~~~~~~~                
selling_rna.cpp:38:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()-1)
     ^~~
selling_rna.cpp: In function 'void add_rev(std::__cxx11::string, int)':
selling_rna.cpp:7:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, u, v) for (int i = u; i <= v; i++)
selling_rna.cpp:49:9:
     FOR(i, 0, s.size()-1)
         ~~~~~~~~~~~~~~~~                
selling_rna.cpp:49:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()-1)
     ^~~
selling_rna.cpp: In function 'std::pair<int, int> getRange(std::__cxx11::string)':
selling_rna.cpp:7:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, u, v) for (int i = u; i <= v; i++)
selling_rna.cpp:84:9:
     FOR(i, 0, s.size()-1)
         ~~~~~~~~~~~~~~~~                
selling_rna.cpp:84:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()-1)
     ^~~
selling_rna.cpp: In function 'int getAns(std::__cxx11::string, std::pair<int, int>)':
selling_rna.cpp:7:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, u, v) for (int i = u; i <= v; i++)
selling_rna.cpp:95:9:
     FOR(i, 0, s.size()-1)
         ~~~~~~~~~~~~~~~~                
selling_rna.cpp:95:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()-1)
     ^~~

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