oj.uz

Submission #298601

# Submission time Handle Problem Language Result Execution time Memory
298601 2020-09-13T11:50:12 Z BeanZ Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 592 ms 175864 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;
        }
        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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50432 KB Output is correct
2 Correct 35 ms 50552 KB Output is correct
3 Correct 35 ms 50424 KB Output is correct
4 Correct 34 ms 50432 KB Output is correct
5 Correct 35 ms 50424 KB Output is correct
6 Correct 35 ms 50560 KB Output is correct
7 Correct 36 ms 50432 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 175864 KB Output is correct
2 Correct 284 ms 169464 KB Output is correct
3 Correct 132 ms 74364 KB Output is correct
4 Correct 133 ms 77432 KB Output is correct
5 Correct 203 ms 130880 KB Output is correct
6 Correct 202 ms 131960 KB Output is correct
7 Correct 157 ms 73208 KB Output is correct
8 Correct 283 ms 115448 KB Output is correct
9 Correct 242 ms 108536 KB Output is correct
10 Correct 195 ms 104696 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 51824 KB Output is correct
2 Correct 90 ms 51832 KB Output is correct
3 Correct 105 ms 52088 KB Output is correct
4 Correct 88 ms 51972 KB Output is correct
5 Correct 94 ms 52088 KB Output is correct
6 Correct 108 ms 52248 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50432 KB Output is correct
2 Correct 35 ms 50552 KB Output is correct
3 Correct 35 ms 50424 KB Output is correct
4 Correct 34 ms 50432 KB Output is correct
5 Correct 35 ms 50424 KB Output is correct
6 Correct 35 ms 50560 KB Output is correct
7 Correct 36 ms 50432 KB Output is correct
8 Correct 284 ms 175864 KB Output is correct
9 Correct 284 ms 169464 KB Output is correct
10 Correct 132 ms 74364 KB Output is correct
11 Correct 133 ms 77432 KB Output is correct
12 Correct 203 ms 130880 KB Output is correct
13 Correct 202 ms 131960 KB Output is correct
14 Correct 157 ms 73208 KB Output is correct
15 Correct 283 ms 115448 KB Output is correct
16 Correct 242 ms 108536 KB Output is correct
17 Correct 195 ms 104696 KB Output is correct
18 Correct 112 ms 51824 KB Output is correct
19 Correct 90 ms 51832 KB Output is correct
20 Correct 105 ms 52088 KB Output is correct
21 Correct 88 ms 51972 KB Output is correct
22 Correct 94 ms 52088 KB Output is correct
23 Correct 108 ms 52248 KB Output is correct
24 Correct 371 ms 158712 KB Output is correct
25 Correct 462 ms 158840 KB Output is correct
26 Correct 327 ms 157432 KB Output is correct
27 Correct 201 ms 77048 KB Output is correct
28 Correct 592 ms 89072 KB Output is correct
29 Correct 266 ms 63452 KB Output is correct