oj.uz

Submission #918893

# Submission time Handle Problem Language Result Execution time Memory
918893 2024-01-30T17:19:19 Z phamducminh Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 221 ms 222216 KB 
//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;






///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


    // file("tbrackets");







    long long t;


    // cin >> t;

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///


int val(char c) {
    switch(c) {
        case 'A': return 0;
        case 'G': return 1;
        case 'C': return 2;
        default: return 3;
    }
}


int n,q;


struct Trie {
    struct Node{

        Node* child[4];
        int cnt,exist,l,r;


        Node() {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
            cnt=exist==0;
            l=n; r=0;
        }
    };

    Node* root= new Node();

    void insert(string x, int id){
        Node* p=root;
        for (char ch: x){

            int c=val(ch);
            if (p->child[c]==nullptr){
                p->child[c]=new Node();
            }
            p=p->child[c];
            p->cnt++;
            p->l=min(p->l,id);
            p->r=max(p->r,id);

        }
        p->exist++;
    }


    pair<int,int> check(string s) {
        Node* p = root;
        pair<int,int> ans={0,n};
        for (auto f : s) {
            int c = val(f);
            if (p->child[c] == nullptr) return ans;
            p = p->child[c];

            ans.first=max(ans.first,p->l);
            ans.second=min(ans.second,p->r);


        }
        return ans;
    }
};


struct reverseTrie {
    struct Node{

        Node* child[4];
        int cnt,exist;
        vector<int> luu;


        Node() {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
            cnt=exist==0;
        }
    };

    Node* root= new Node();

    void insert(string x, int id){
        Node* p=root;
        reverse(all(x));

        for (char ch: x){

            int c=val(ch);
            if (p->child[c]==nullptr){
                p->child[c]=new Node();
            }
            p=p->child[c];
            p->cnt++;
            p->luu.push_back(id);

        }
        p->exist++;
    }


    int query(string s, pair<int,int> range) {
        Node* p = root;
        pair<int,int> ans={0,n};
        reverse(all(s));
        for (auto f : s) {
            int c = val(f);
            if (p->child[c] == nullptr) return 0;
            p = p->child[c];

            

        }

        int l=lower_bound(all(p->luu),range.first)-(p->luu).begin();
        int r=upper_bound(all(p->luu),range.second)-(p->luu).begin()-1;

        

        return r-l+1;
    }
};



Trie a;
reverseTrie b;

void solve(){

    
    
    string s[100009];

    cin >> n >> q;


    for (int i=1; i<=n; i++){


        cin >> s[i];


    }

    sort(s+1,s+n+1);

    for (int i=1; i<=n; i++) a.insert(s[i],i),b.insert(s[i],i);

    while (q--){


        string s1,s2;

        cin >> s1 >> s2;

        auto tam=a.check(s1);

        if (!tam.first) {cout << 0 << "\n"; continue;}


        cout << b.query(s2,tam) << "\n";
    }
    
        
}

Compilation message

selling_rna.cpp: In member function 'int reverseTrie::query(std::string, std::pair<int, int>)':
selling_rna.cpp:215:23: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  215 |         pair<int,int> ans={0,n};
      |                       ^~~
selling_rna.cpp: In constructor 'Trie::Node::Node()':
selling_rna.cpp:135:17: warning: '*<unknown>.Trie::Node::exist' is used uninitialized in this function [-Wuninitialized]
  135 |             cnt=exist==0;
      |                 ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3416 KB Output is correct
7 Correct 2 ms 3416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 222216 KB Output is correct
2 Correct 221 ms 212008 KB Output is correct
3 Correct 123 ms 140660 KB Output is correct
4 Correct 122 ms 134748 KB Output is correct
5 Correct 196 ms 215888 KB Output is correct
6 Correct 195 ms 219104 KB Output is correct
7 Correct 51 ms 16720 KB Output is correct
8 Correct 173 ms 137372 KB Output is correct
9 Correct 144 ms 117188 KB Output is correct
10 Correct 103 ms 113076 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4844 KB Output is correct
2 Correct 16 ms 4952 KB Output is correct
3 Correct 19 ms 4868 KB Output is correct
4 Correct 15 ms 4440 KB Output is correct
5 Correct 17 ms 4728 KB Output is correct
6 Correct 21 ms 4772 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3416 KB Output is correct
7 Correct 2 ms 3416 KB Output is correct
8 Correct 206 ms 222216 KB Output is correct
9 Correct 221 ms 212008 KB Output is correct
10 Correct 123 ms 140660 KB Output is correct
11 Correct 122 ms 134748 KB Output is correct
12 Correct 196 ms 215888 KB Output is correct
13 Correct 195 ms 219104 KB Output is correct
14 Correct 51 ms 16720 KB Output is correct
15 Correct 173 ms 137372 KB Output is correct
16 Correct 144 ms 117188 KB Output is correct
17 Correct 103 ms 113076 KB Output is correct
18 Correct 20 ms 4844 KB Output is correct
19 Correct 16 ms 4952 KB Output is correct
20 Correct 19 ms 4868 KB Output is correct
21 Correct 15 ms 4440 KB Output is correct
22 Correct 17 ms 4728 KB Output is correct
23 Correct 21 ms 4772 KB Output is correct
24 Correct 186 ms 184152 KB Output is correct
25 Correct 193 ms 184148 KB Output is correct
26 Correct 177 ms 182096 KB Output is correct
27 Correct 110 ms 117332 KB Output is correct
28 Correct 135 ms 40016 KB Output is correct
29 Correct 61 ms 10440 KB Output is correct