oj.uz

Submission #298591

# Submission time Handle Problem Language Result Execution time Memory
298591 2020-09-13T10:08:07 Z BeanZ Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 960 ms 175740 KB 
#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;
        }
        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("A.INP", "r")){
                freopen("A.INP", "r", stdin);
                freopen("A.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;
                //cout << l << " " << r << endl;
                if (l > r){
                        cout << 0 << endl;
                        continue;
                }
                reverse(p.begin(), p.end());
                cout << get(p, l, r) << endl;
        }
}
/*
5
1
AGG
AUUG
AUCCG
AUCCUG
UG
UG UG
*/

Compilation message

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:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   45 |         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:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   52 |         for (int i = 0; i < min(t.size(), p.size()); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |                 freopen("A.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:63:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   63 |                 freopen("A.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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 50432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 175740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 51952 KB Output is correct
2 Incorrect 166 ms 51840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 50432 KB Output isn't correct
2 Halted 0 ms 0 KB -