Submission #1110391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110391		FucKanh	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	282 ms	200740 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

const int maxn = 1e5 + 2;

string a[maxn];
int idx[300];

struct node1 {
    vector<int> t;
    node1 *chr[4];
    node1() {
        for (int i = 0; i < 4;i++) {
            chr[i] = nullptr;
        }
    }
};

struct node2 {
    int tmax=0,tmin=1e9;
    node2 *chr[4];
    node2() : tmax(0), tmin((int)1e9) {
        for (int i = 0; i < 4;i++) {
            chr[i] = nullptr;
        }
    }
};

struct trie1 {
    node2 *root = new node2();
    void update(node2 *p, string &s, int pos, int id) {
        p->tmin = min(p->tmin, id);
        p->tmax = max(p->tmax, id);
        if (pos == s.size()) return;
        if (p->chr[idx[s[pos]]] == nullptr) {
            p->chr[idx[s[pos]]] = new node2();
        }
        update(p->chr[idx[s[pos]]],s,pos+1,id);
    }
    pii get(node2 *p, string &s, int pos) {
        if (p==nullptr) return {-1,-1};
        if (pos==s.size()) return {p->tmin,p->tmax};
        return get(p->chr[idx[s[pos]]], s, pos+1);
    }
    pii get(string &s) {
        return get(root,s,0);
    }
    void update(string &s, int id) {
        update(root,s,0,id);
    }
};

struct trie2 {
    node1 *root = new node1();
    void update(node1 *p, string &s, int pos, int id) {
        (p->t).push_back(id);
        if (pos == -1) return;
        if (p->chr[idx[s[pos]]] == nullptr) {
            p->chr[idx[s[pos]]] = new node1();
        }
        update(p->chr[idx[s[pos]]],s,pos-1,id);
    }
    void sortnode(node1 *p) {
        sort(p->t.begin(),p->t.end());
        for (int i = 0; i < 4; i++) {
            if (p->chr[i] != nullptr) {
                sortnode(p->chr[i]);
            }
        }
    }
    int get(node1 *p, string &s, int pos, int mn, int mx) {
//        cerr << "get: "<< pos << " " << s[pos] << '\n';
        if (p==nullptr) return 0;
        if (pos==-1) {
            int l = lower_bound(p->t.begin(),p->t.end(),mn) - p->t.begin();
            int r = upper_bound(p->t.begin(),p->t.end(),mx) - p->t.begin();
//            cerr << "::: "; for (int v : p->t) cerr << v << " "; cerr << '\n';
            return r-l;
        }
        return get(p->chr[idx[s[pos]]],s,pos-1,mn,mx);
    }
    int get(string &s, int mn, int mx) {
        return get(root,s,s.size()-1,mn,mx);
    }
    void update(string &s, int id) {
        update(root,s,s.size()-1,id);
    }
};

trie1 pre;
trie2 suf;

void solve() {
    idx['A'] = 0;
    idx['C'] = 1;
    idx['G'] = 2;
    idx['U'] = 3;
    int n,m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
//        cerr << "add:" << a[i] << endl;
        pre.update(a[i],i);
        suf.update(a[i],i);
    }
    suf.sortnode(suf.root);
    for (int i = 1; i <= m; i++) {
        string p,s; cin >> p >> s;
        pii pos = pre.get(p);
//        cerr << ": " << pos.first << " " << pos.second << '\n';
        cout << suf.get(s,pos.first,pos.second) << '\n';
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie1::update(node2*, std::string&, long long int, long long int)':
selling_rna.cpp:38:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if (pos == s.size()) return;
      |             ~~~~^~~~~~~~~~~
selling_rna.cpp:39:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |         if (p->chr[idx[s[pos]]] == nullptr) {
      |                              ^
selling_rna.cpp:40:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |             p->chr[idx[s[pos]]] = new node2();
      |                              ^
selling_rna.cpp:42:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |         update(p->chr[idx[s[pos]]],s,pos+1,id);
      |                                 ^
selling_rna.cpp: In member function 'std::pair<long long int, long long int> trie1::get(node2*, std::string&, long long int)':
selling_rna.cpp:46:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (pos==s.size()) return {p->tmin,p->tmax};
      |             ~~~^~~~~~~~~~
selling_rna.cpp:47:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |         return get(p->chr[idx[s[pos]]], s, pos+1);
      |                                     ^
selling_rna.cpp: In member function 'void trie2::update(node1*, std::string&, long long int, long long int)':
selling_rna.cpp:62:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |         if (p->chr[idx[s[pos]]] == nullptr) {
      |                              ^
selling_rna.cpp:63:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |             p->chr[idx[s[pos]]] = new node1();
      |                              ^
selling_rna.cpp:65:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |         update(p->chr[idx[s[pos]]],s,pos-1,id);
      |                                 ^
selling_rna.cpp: In member function 'long long int trie2::get(node1*, std::string&, long long int, long long int, long long int)':
selling_rna.cpp:84:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |         return get(p->chr[idx[s[pos]]],s,pos-1,mn,mx);
      |                                     ^

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