Submission #419180

#	Time	Username	Problem	Language	Result	Execution time	Memory
419180		cpp219	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	353 ms	243644 KiB

selling_rna

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
string s[N],rs[N];
ll n,Q;

char Convert(char c){
    if (c == 'A') return '0';
    if (c == 'G') return '1';
    if (c == 'C') return '2';
    if (c == 'U') return '3';
}

void oper(string &s){
    for (ll j = 0;j < s.size();j++) s[j] = Convert(s[j]);
}

struct Trie{
    Trie *child[4];
    ll l,r;
    vector<ll> v;
    Trie(){
        l = inf; r = 0;
        for (ll i = 0;i < 4;i++) child[i] = NULL;
    }
    void Add1(ll id,string &s,ll pos){
        l = min(l,pos); r = max(r,pos);
        if (id == s.size()) return;
        ll x = s[id] - '0';
        if (!child[x]) child[x] = new Trie;
        child[x] -> Add1(id + 1,s,pos);
    }
    void Add2(ll id,string&s,ll pos){
        v.push_back(pos);
        if (id == s.size()) return;
        ll x = s[id] - '0';
        if (!child[x]) child[x] = new Trie;
        child[x] -> Add2(id + 1,s,pos);
    }
    void TravelSort(){
        sort(v.begin(),v.end());
        for (ll i = 0;i < 4;i++) if (child[i])
            child[i] -> TravelSort();
    }
    LL getPair(ll id,string&s){
        if (id == s.size()) return {l,r};
        ll x = s[id] - '0';
        if (child[x]) return child[x] -> getPair(id + 1,s);
        return {-1,-1};
    }
    ll GetAns(ll id,string &s,ll L,ll R){
        if (id == s.size()){
            //cout<<v.size()<<"x"; exit(0);
            //for (auto i : v) cout<<i<<" "; exit(0);
            ll p = lower_bound(v.begin(),v.end(),L) - v.begin();
            ll q = upper_bound(v.begin(),v.end(),R) - v.begin() - 1;
            return max(0,q - p + 1);
        }
        ll x = s[id] - '0';
        if (child[x]) return child[x] -> GetAns(id + 1,s,L,R);
        return 0;
    }
};
string p,q;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    Trie Tree1,Tree2; /// 1 for origin   2 for reversed
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++) cin>>s[i],oper(s[i]);
    sort(s + 1,s + n + 1);
    for (ll i = 1;i <= n;i++){
        rs[i] = s[i];
        reverse(rs[i].begin(),rs[i].end());
        Tree1.Add1(0,s[i],i); Tree2.Add2(0,rs[i],i);
    }
    Tree2.TravelSort();
    while(Q--){
        cin>>p>>q; oper(p); oper(q);
        reverse(q.begin(),q.end());
        LL now = Tree1.getPair(0,p); //cout<<now.fs<<" "<<now.sc; return 0;
        cout<<Tree2.GetAns(0,q,now.fs,now.sc)<<"\n";
    }
}

Compilation message (stderr)

selling_rna.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
selling_rna.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
selling_rna.cpp: In function 'void oper(std::string&)':
selling_rna.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (ll j = 0;j < s.size();j++) s[j] = Convert(s[j]);
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::Add1(int, std::string&, int)':
selling_rna.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if (id == s.size()) return;
      |             ~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::Add2(int, std::string&, int)':
selling_rna.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (id == s.size()) return;
      |             ~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'LL Trie::getPair(int, std::string&)':
selling_rna.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (id == s.size()) return {l,r};
      |             ~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::GetAns(int, std::string&, int, int)':
selling_rna.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (id == s.size()){
      |             ~~~^~~~~~~~~~~
selling_rna.cpp: In function 'char Convert(char)':
selling_rna.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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