Submission #298601

#	Time	Username	Problem	Language	Result	Execution time	Memory
298601		BeanZ	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	592 ms	175864 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
string s[N];
char c[4] = {'A', 'G', 'C', 'U'};
ll dp[2000005][4];
ll timer = 1;
vector<ll> node[2000005];
void add(string t, ll id){
        ll now = 1;
        for (int i = 0; i < t.length(); i++){
                ll a;
                for (int j = 0; j < 4; j++){
                        if (t[i] == c[j]) a = j;
                }
                if (dp[now][a] == 0){
                        timer++;
                        dp[now][a] = timer;
                }
                now = dp[now][a];
                node[now].push_back(id);
        }
}
ll get(string t, ll l, ll r){
        ll now = 1;
        for (int i = 0; i < t.length(); i++){
                ll a;
                for (int j = 0; j < 4; j++){
                        if (t[i] == c[j]) a = j;
                }
                now = dp[now][a];
        }
        /*
        ll res = 0;
        for (auto j : node[now]){
                if (j >= l && j <= r) res++;
        }
        return res;*/
        return upper_bound(node[now].begin(), node[now].end(), r) - lower_bound(node[now].begin(), node[now].end(), l);
}
bool cmpsmaller(string t, string p){
        for (int i = 0; i < min(t.size(), p.size()); i++){
                if (t[i] < p[i]) return true;
                if (t[i] > p[i]) return false;
        }
        if (t.length() < p.length()) return true;
        return false;
}
bool cmpgreater(string t, string p){
        for (int i = 0; i < min(t.size(), p.size()); i++){
                if (t[i] > p[i]) return true;
                if (t[i] < p[i]) return false;
        }
        return false;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("test.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.out", "w", stdout);
        }
        ll n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
                cin >> s[i];
        }
        sort(s + 1, s + n + 1);
        for (int i = 1; i <= n; i++){
                reverse(s[i].begin(), s[i].end());
                add(s[i], i);
                reverse(s[i].begin(), s[i].end());
        }
        while (m--){
                string t, p;
                cin >> t >> p;
                ll lo = 1, hi = n;
                while (lo <= hi){
                        ll mid = (lo + hi) >> 1;
                        if (cmpsmaller(s[mid], t)) lo = mid + 1;
                        else hi = mid - 1;
                }
                ll l = lo;
                lo = 1, hi = n;
                while (lo <= hi){
                        ll mid = (lo + hi) >> 1;
                        if (cmpgreater(s[mid], t)) hi = mid - 1;
                        else lo = mid + 1;
                }
                ll r = hi;
                if (l > r){
                        cout << 0 << endl;
                        continue;
                }
                reverse(p.begin(), p.end());
                cout << get(p, l, r) << endl;
        }
}
/*
*/

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::string, long long int)':
selling_rna.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i = 0; i < t.length(); i++){
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'long long int get(std::string, long long int, long long int)':
selling_rna.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i < t.length(); i++){
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'bool cmpsmaller(std::string, std::string)':
selling_rna.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   46 |         for (int i = 0; i < min(t.size(), p.size()); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool cmpgreater(std::string, std::string)':
selling_rna.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   54 |         for (int i = 0; i < min(t.size(), p.size()); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:64:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   64 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:65:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |                 freopen("test.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'long long int get(std::string, long long int, long long int)':
selling_rna.cpp:35:21: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |                 now = dp[now][a];
      |                 ~~~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void add(std::string, long long int)':
selling_rna.cpp:22:36: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |                         dp[now][a] = timer;
      |                         ~~~~~~~~~~~^~~~~~~

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