Submission #839587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
839587	2023-08-30T09:07:58 Z	vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++14	Compilation error	0 ms	0 KB

selling_rna

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define setpre(i) setprecision(i)<<fixed
#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 mp make_pair
#define moo cout<<"moo "
#define fi first
#define se second

ll lmod = 1e9 + 7;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int, int> ii;
typedef pair<double, double> dd;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<string> s;

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

struct node{
    int next[4];
    int l, r;
    node(){
        memset(next, -1, sizeof next);
        l = INT_MAX;
        r = -1;
    }
};

struct node2{
    int next[4];
    ordered_set os;
    node2(){
        memset(next, -1, sizeof next);
    }    
};

struct {
    vector<node> t;

    void init(){
        t.emplace_back();
    }
    
    void insert(int id){
        int ptr = 0;
        for(char c: s[id]){
            if(t[ptr].next[getid(c)] == -1){
                t.emplace_back();
                t[ptr].next[getid(c)] = t.size() - 1;
            }
            ptr = t[ptr].next[getid(c)];
            t[ptr].l = min(t[ptr].l, id);
            t[ptr].r = max(t[ptr].l, id);
        }
    }

    int traverse(string z){
        int ptr = 0;
        for(char c: z){
            if(t[ptr].next[getid(c)] == -1) return -1;
            ptr = t[ptr].next[getid(c)];
        }
        return ptr;
    }

} trie1;

struct {
    vector<node2> t;

    void init(){
        t.emplace_back();
    }
    
    void insert(int id){
        int ptr = 0;
        for(char c: s[id]){
            if(t[ptr].next[getid(c)] == -1){
                t.emplace_back();
                t[ptr].next[getid(c)] = t.size() - 1;
            }
            ptr = t[ptr].next[getid(c)];
            t[ptr].os.insert(id);
        }
        
    }

    int traverse(string z){
        int ptr = 0;
        for(char c: z){
            if(t[ptr].next[getid(c)] == -1) return -1;
            ptr = t[ptr].next[getid(c)];
        }
        return ptr;
    }

    
} trie2;

int main(){
	// freopen("input.inp", "r", stdin);
	// freopen("output.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    foru(i, 1, n){
        string z; cin >> z;
        s.pb(z);
    }
    trie1.init(); trie2.init();
    sort(s.begin(), s.end());
    // for(auto z: s) cout << z << endl;
    foru(i, 0, n - 1) {
        trie1.insert(i);
        reverse(s[i].begin(), s[i].end());
        trie2.insert(i);
    }
    while(q--){
        string z, t; cin >> z >> t;
        reverse(t.begin(), t.end());
        int a = trie1.traverse(z);
        int b = trie2.traverse(t);
        if(a == -1 or b == -1){
            cout << 0 << endl; continue;
        }
        // for(int i: trie2.t[b].os) cout << i << " ";
        // cout << endl;
        int l = trie1.t[a].l;
        int r = trie1.t[a].r;
        // moo << l << " " << r << endl;
        cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
    }
//	fclose(stdout);
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:151:92: error: no matching function for call to 'max(__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >*, int, int*, const int*, int&, const int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >*, int, int*, const int*, int&, const int&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >*, int, int*, const int*, int&, const int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<int, long unsigned int, std::allocator<char> >*, int, int*, const int*, int&, const int&, true, std::allocator<char> >, std::allocator<char> >, std::less<int>, std::allocator<char> >::size_type, long long unsigned int)'
  151 |         cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from selling_rna.cpp:7:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
selling_rna.cpp:151:92: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'long long unsigned int')
  151 |         cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from selling_rna.cpp:7:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
selling_rna.cpp:151:92: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'long long unsigned int')
  151 |         cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from selling_rna.cpp:7:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
selling_rna.cpp:151:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  151 |         cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from selling_rna.cpp:7:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
selling_rna.cpp:151:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  151 |         cout << max(trie2.t[b].os.order_of_key(r + 1) - trie2.t[b].os.order_of_key(l), 0ULL) << endl;
      |                                                                                            ^