oj.uz

Submission #839474

# Submission time Handle Problem Language Result Execution time Memory
839474 2023-08-30T06:08:53 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 254 ms 232056 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair <int,int> pii;
int n,m;
struct trie{
    int cv(char x){
        if (x == 'A')return 0;
        if (x == 'G')return 1;
        if (x == 'C')return 2;
        return 3;
    }
    struct node{
        node* c[4];
        int in,out;
    };

    node* new_node(){
        node* res = new node;
        for (int i = 0;i < 4;i ++)res -> c[i] = nullptr;
        res -> in = 0;
        res -> out = 0;
        return res;
    }
    node* root = new_node();
    void ins(string s){
        node* cur = root;
        for (int i = 0;i < s.size();i ++){
            if (cur -> c[cv(s[i])] == nullptr){
                cur -> c[cv(s[i])] = new_node();
            }
            cur = cur -> c[cv(s[i])];
        }
    }
    pii ask(string s){
        node* cur = root;
        for (int i = 0;i < s.size();i ++){
            if (cur -> c[cv(s[i])] == nullptr){
                return {-1,-1};
            }
            cur = cur -> c[cv(s[i])];
        }
        return {cur->in,cur->out};
    }
    int timeDFS = 0;
    void dfs(node* cur){
        cur -> in = ++timeDFS;
        for (int i = 0;i < 4;i++){
            if (cur -> c[i] != nullptr)dfs(cur->c[i]);
        }
        cur -> out = timeDFS;
    }
};
trie a,rev_a;
string s[100100];
string rev_s[100100];
string p[100100],q[100100];
const int MAXSZ = 2e6;
vector <int> g[2000100];
struct query{
    int l,r,id;
};
vector <query> all[2000100];
int BIT[MAXSZ + 100];
int ans[100100];
void upd(int x){
    for (;x <= MAXSZ;x += x & -x){
        BIT[x]++;
    }
}
int get(int x){
    int res = 0;
    for (;x>0;x-=x&-x){
        res += BIT[x];
    }
    return res;
}
int ask(int l,int r){
    return get(r) - get(l-1);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (int i = 1;i <= n;i ++){
        cin>>s[i];
        a.ins(s[i]);
        rev_s[i] = s[i];
        reverse(rev_s[i].begin(),rev_s[i].end());
        rev_a.ins(rev_s[i]);
    }
    a.dfs(a.root);
    rev_a.dfs(rev_a.root);
    for (int i = 1;i <= n;i ++){
        //cout<<a.ask(s[i]).fi<<' '<<rev_a.ask(rev_s[i]).fi<<'\n';
        g[a.ask(s[i]).fi].push_back(rev_a.ask(rev_s[i]).fi);
    }
    for (int i = 1;i <= m;i ++){
        cin>>p[i]>>q[i];
        pii x = a.ask(p[i]);
        reverse(q[i].begin(),q[i].end());
        pii y = rev_a.ask(q[i]);
        //cout<<x.fi<<' '<<x.se<<' '<<y.fi<<' '<<y.se<<'\n';
        if (x.fi != -1 && y.fi != -1){
            all[x.second].push_back({y.first,y.second,i});
            all[x.first - 1].push_back({y.first,y.second,-i});
        }
    }
    for (int i = 1;i <= MAXSZ;i ++){
        for (auto x:g[i]){
            upd(x);
        }
        for (auto x:all[i]){
            if (x.id < 0){
                ans[-x.id] -= ask(x.l,x.r);
            }
            else{
                ans[x.id] += ask(x.l,x.r);
            }
        }
    }
    for (int i = 1;i <= m;i ++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Compilation message

selling_rna.cpp: In member function 'void trie::ins(std::string)':
selling_rna.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0;i < s.size();i ++){
      |                        ~~^~~~~~~~~~
selling_rna.cpp: In member function 'pii trie::ask(std::string)':
selling_rna.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = 0;i < s.size();i ++){
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 106828 KB Output is correct
2 Correct 49 ms 106744 KB Output is correct
3 Correct 49 ms 106828 KB Output is correct
4 Correct 56 ms 106828 KB Output is correct
5 Correct 49 ms 106828 KB Output is correct
6 Correct 50 ms 106804 KB Output is correct
7 Correct 49 ms 106820 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 212840 KB Output is correct
2 Correct 187 ms 208200 KB Output is correct
3 Correct 193 ms 204568 KB Output is correct
4 Correct 188 ms 200140 KB Output is correct
5 Correct 254 ms 230204 KB Output is correct
6 Correct 242 ms 232056 KB Output is correct
7 Correct 102 ms 114560 KB Output is correct
8 Correct 169 ms 185164 KB Output is correct
9 Correct 158 ms 173904 KB Output is correct
10 Correct 140 ms 169560 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 109140 KB Output is correct
2 Correct 64 ms 108748 KB Output is correct
3 Correct 71 ms 109236 KB Output is correct
4 Correct 62 ms 108364 KB Output is correct
5 Correct 66 ms 108624 KB Output is correct
6 Correct 67 ms 108732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 106828 KB Output is correct
2 Correct 49 ms 106744 KB Output is correct
3 Correct 49 ms 106828 KB Output is correct
4 Correct 56 ms 106828 KB Output is correct
5 Correct 49 ms 106828 KB Output is correct
6 Correct 50 ms 106804 KB Output is correct
7 Correct 49 ms 106820 KB Output is correct
8 Correct 200 ms 212840 KB Output is correct
9 Correct 187 ms 208200 KB Output is correct
10 Correct 193 ms 204568 KB Output is correct
11 Correct 188 ms 200140 KB Output is correct
12 Correct 254 ms 230204 KB Output is correct
13 Correct 242 ms 232056 KB Output is correct
14 Correct 102 ms 114560 KB Output is correct
15 Correct 169 ms 185164 KB Output is correct
16 Correct 158 ms 173904 KB Output is correct
17 Correct 140 ms 169560 KB Output is correct
18 Correct 68 ms 109140 KB Output is correct
19 Correct 64 ms 108748 KB Output is correct
20 Correct 71 ms 109236 KB Output is correct
21 Correct 62 ms 108364 KB Output is correct
22 Correct 66 ms 108624 KB Output is correct
23 Correct 67 ms 108732 KB Output is correct
24 Correct 176 ms 196044 KB Output is correct
25 Correct 186 ms 197644 KB Output is correct
26 Correct 171 ms 194500 KB Output is correct
27 Correct 176 ms 188748 KB Output is correct
28 Correct 149 ms 130132 KB Output is correct
29 Correct 99 ms 111180 KB Output is correct