oj.uz

Submission #725728

# Submission time Handle Problem Language Result Execution time Memory
725728 2023-04-18T01:07:17 Z Cookie Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 358 ms 193540 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 1e5, mxm = 1e5;
int n, m, ans = 0;
string s[mxn + 1], t[mxn + 1];
int to[1005];
struct Node1{
    Node1 *nxt[4];
    int l = n + 1, r = -1;
    Node1(){
        for(int i = 0; i < 4; i++)nxt[i] = NULL;
    }
};
struct Node2{
    Node2 *nxt[4];
    vt<int>pos;
    Node2(){
        forr(i, 0, 4)nxt[i] = NULL;
    }
};
Node1 *root = new Node1();
Node2 *root2 = new Node2();

void add1(string s, int id){
    Node1 *nd = root;
    for(int i = 0; i < s.size(); i++){
        int c = to[s[i]];
        if(nd->nxt[c] == NULL){
            nd->nxt[c] = new Node1();
        }
        nd->nxt[c]->l = min(nd->nxt[c]->l, id); nd->nxt[c]->r = max(nd->nxt[c]->r, id);
        nd = nd->nxt[c];
    }
}
void add2(string s, int id){
    Node2 *nd = root2;
    for(int i = 0; i < s.size(); i++){
        int c = to[s[i]];
        if(nd->nxt[c] == NULL){
            nd->nxt[c] = new Node2();
        }
        nd->nxt[c]->pos.pb(id);
        nd = nd->nxt[c];
    }
}
pii get1(string s){
    Node1 *nd = root;
    for(int i = 0; i < s.size(); i++){
        int c = to[s[i]];
        if(nd->nxt[c] == NULL)return(make_pair(-1, -1));
        nd = nd->nxt[c];
    }
    return(make_pair(nd->l, nd->r));
    
}
int get2(string s, int l, int r){
    
    Node2 *nd = root2;
    for(int i = 0; i < s.size(); i++){
        int c = to[s[i]];
        if(nd->nxt[c] == NULL){
            
            return(0);
        }
        nd = nd->nxt[c];
    }
    vt<int>v = nd->pos;
    
    return(upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l));
}
signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, n)cin >> s[i];
    to['A'] = 0; to['U'] = 1; to['C'] = 2; to['G'] = 3;
    sort(s, s + n);
    for(int i = 0; i < n; i++){
        
        add1(s[i], i);
        reverse(s[i].begin(), s[i].end());
        add2(s[i], i);
    }
    forr(i, 0, m){
        string p, q; cin >> p >> q;
        reverse(q.begin(), q.end());
        auto [l, r] = get1(p);
        
        cout << get2(q, l, r) << "\n";
        
    }
    return(0);
}

Compilation message

selling_rna.cpp: In function 'void add1(std::string, int)':
selling_rna.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp:43:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         int c = to[s[i]];
      |                        ^
selling_rna.cpp: In function 'void add2(std::string, int)':
selling_rna.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp:54:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |         int c = to[s[i]];
      |                        ^
selling_rna.cpp: In function 'std::pair<int, int> get1(std::string)':
selling_rna.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp:65:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |         int c = to[s[i]];
      |                        ^
selling_rna.cpp: In function 'int get2(std::string, int, int)':
selling_rna.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp:76:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |         int c = to[s[i]];
      |                        ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         auto [l, r] = get1(p);
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6596 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6616 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 193540 KB Output is correct
2 Correct 203 ms 187496 KB Output is correct
3 Correct 136 ms 115032 KB Output is correct
4 Correct 136 ms 110168 KB Output is correct
5 Correct 162 ms 181788 KB Output is correct
6 Correct 180 ms 184348 KB Output is correct
7 Correct 76 ms 22248 KB Output is correct
8 Correct 190 ms 121036 KB Output is correct
9 Correct 165 ms 104408 KB Output is correct
10 Correct 126 ms 99276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 7484 KB Output is correct
2 Correct 38 ms 7884 KB Output is correct
3 Correct 45 ms 7868 KB Output is correct
4 Correct 45 ms 7608 KB Output is correct
5 Correct 58 ms 7912 KB Output is correct
6 Correct 98 ms 7812 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6596 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6616 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 192 ms 193540 KB Output is correct
9 Correct 203 ms 187496 KB Output is correct
10 Correct 136 ms 115032 KB Output is correct
11 Correct 136 ms 110168 KB Output is correct
12 Correct 162 ms 181788 KB Output is correct
13 Correct 180 ms 184348 KB Output is correct
14 Correct 76 ms 22248 KB Output is correct
15 Correct 190 ms 121036 KB Output is correct
16 Correct 165 ms 104408 KB Output is correct
17 Correct 126 ms 99276 KB Output is correct
18 Correct 145 ms 7484 KB Output is correct
19 Correct 38 ms 7884 KB Output is correct
20 Correct 45 ms 7868 KB Output is correct
21 Correct 45 ms 7608 KB Output is correct
22 Correct 58 ms 7912 KB Output is correct
23 Correct 98 ms 7812 KB Output is correct
24 Correct 199 ms 163724 KB Output is correct
25 Correct 218 ms 163968 KB Output is correct
26 Correct 188 ms 161908 KB Output is correct
27 Correct 144 ms 97216 KB Output is correct
28 Correct 358 ms 41856 KB Output is correct
29 Correct 109 ms 15008 KB Output is correct