oj.uz

Submission #896270

# Submission time Handle Problem Language Result Execution time Memory
896270 2024-01-01T07:04:14 Z Minhbao Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 253 ms 275064 KB 
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = double;
using str = string;
 
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
// #define mp make_pair
#define f first
#define s second
 
// vectors
// size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
// #define rtn return
 
#define lb lower_bound
#define ub upper_bound
 
/* Some Codes Skipped */
 
// loops
#define FOR(i,a,b) for (int (i) = (a); (i) < (b); ++(i))
#define REP(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int (i) = (b)-1; (i) >= (a); --(i))
#define PER(i,a) ROF(i,0,a)
#define rep(a) REP(_,a)
#define each(a,x) for (auto& a: x)
 
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};   // for every grid problem
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
    sort(all(v)); v.erase(unique(all(v)),end(v)); }
// Some Codes Skipped
 
inline namespace FileIO {
    void setIn(str s) {freopen(s.c_str(),"r", stdin);}
    void setOut(str s) {freopen(s.c_str(),"w", stdout);}
    void setIO() {
        cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
		 
        // cin.exceptions(cin.failbit);
        // throws exception when do smth illegal
        // ex. try to read letter into int
        // setIn("test.txt"), setOut("output.txt");    // for old USACO
    }
}

const int N=2001000;

const int MAX_VALUE=4;

struct Node {
public:
    Node* child[MAX_VALUE];
    int exist, cnt, num;
    int l, r;
    vector<int> indexes;

    Node(){
        this->exist=0; this->cnt=0; this->num=0;
        this->l=N; this->r=-1;
        for(int i=0;i<MAX_VALUE;++i) this->child[i]=NULL;
    }
};

map<char, int> index2;

struct Trie {
public:
    Node* root;
    Trie(){
        root=new Node();
    }
};

Trie* preTrie;

Trie* sufTrie;

void addString(string s, int stt){
    Node* root=preTrie->root;
    for(int i=0;i<s.size();++i){
        root->cnt+=1;
        root->l=min(root->l, stt);
        root->r=max(root->r, stt);
        int ind=index2[s[i]];
        if(root->child[ind]==NULL){
            root->child[ind]=new Node();
        }
        root=root->child[ind];
    }
    root->cnt+=1;
    root->exist+=1;
    root->l=min(root->l, stt);
    root->r=max(root->r, stt);

    root=sufTrie->root;
    for(int i=s.size()-1;i>=0;--i){
        root->cnt+=1;
        root->indexes.push_back(stt);
        int ind=index2[s[i]];
        if(root->child[ind]==NULL){
            root->child[ind]=new Node();
        }
        root=root->child[ind];
    }
    root->cnt+=1;
    root->exist+=1;
    root->indexes.push_back(stt);
}

struct Item {
public:
    Node* node;
    int n;
    Item(Node* node, int n){
        this->node=node;
        this->n=n;
    }
};

int stringWithPreAndSuf(string p, string q){
    Node* root=preTrie->root;
    for(int i=0;i<p.size();++i){
        int ind=index2[p[i]];
        if(root->child[ind]==NULL) return 0;
        root=root->child[ind];
    }
    
    Node* root2=sufTrie->root;
    for(int i=q.size()-1;i>=0;--i){
        int ind=index2[q[i]];
        if(root2->child[ind]==NULL) return 0;
        root2=root2->child[ind];
    }

    auto left=lower_bound(root2->indexes.begin(), root2->indexes.end(), root->l);
    auto right=upper_bound(root2->indexes.begin(), root2->indexes.end(), root->r);
    if(left==root2->indexes.end()){
        return 0;
    }
    int ans=right-left;
    return ans;
}

void solve(int tc){
    preTrie=new Trie();
    sufTrie=new Trie();
    vector<string> v;
    int n, m; cin>>n>>m;
    for(int i=0;i<n;++i){
        string s; cin>>s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for(int i=0;i<n;++i){
        addString(v[i], i);
    }
    for(int i=0;i<m;++i){
        string p, q; cin>>p>>q;
        cout<<stringWithPreAndSuf(p, q)<<"\n";
    }
}   
 
int main() {
    index2['A']=0;
    index2['C']=1;
    index2['G']=2;
    index2['U']=3;

    setIO();

    int tc=1;
	// cin>>tc;
	
	for(int i=1;i<=tc;++i){
		solve(i);
	}
}

Compilation message

selling_rna.cpp: In function 'void addString(std::string, int)':
selling_rna.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<s.size();++i){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int stringWithPreAndSuf(std::string, std::string)':
selling_rna.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i=0;i<p.size();++i){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void FileIO::setIn(str)':
selling_rna.cpp:75:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     void setIn(str s) {freopen(s.c_str(),"r", stdin);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void FileIO::setOut(str)':
selling_rna.cpp:76:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     void setOut(str s) {freopen(s.c_str(),"w", stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 250704 KB Output is correct
2 Correct 207 ms 240008 KB Output is correct
3 Correct 157 ms 199956 KB Output is correct
4 Correct 151 ms 190828 KB Output is correct
5 Correct 231 ms 270844 KB Output is correct
6 Correct 253 ms 275064 KB Output is correct
7 Correct 51 ms 16216 KB Output is correct
8 Correct 191 ms 170692 KB Output is correct
9 Correct 160 ms 145104 KB Output is correct
10 Correct 124 ms 138704 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3528 KB Output is correct
2 Correct 16 ms 3044 KB Output is correct
3 Correct 20 ms 3288 KB Output is correct
4 Correct 15 ms 3044 KB Output is correct
5 Correct 17 ms 2780 KB Output is correct
6 Correct 21 ms 3260 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 243 ms 250704 KB Output is correct
9 Correct 207 ms 240008 KB Output is correct
10 Correct 157 ms 199956 KB Output is correct
11 Correct 151 ms 190828 KB Output is correct
12 Correct 231 ms 270844 KB Output is correct
13 Correct 253 ms 275064 KB Output is correct
14 Correct 51 ms 16216 KB Output is correct
15 Correct 191 ms 170692 KB Output is correct
16 Correct 160 ms 145104 KB Output is correct
17 Correct 124 ms 138704 KB Output is correct
18 Correct 21 ms 3528 KB Output is correct
19 Correct 16 ms 3044 KB Output is correct
20 Correct 20 ms 3288 KB Output is correct
21 Correct 15 ms 3044 KB Output is correct
22 Correct 17 ms 2780 KB Output is correct
23 Correct 21 ms 3260 KB Output is correct
24 Correct 217 ms 208220 KB Output is correct
25 Correct 222 ms 208588 KB Output is correct
26 Correct 205 ms 205772 KB Output is correct
27 Correct 153 ms 165724 KB Output is correct
28 Correct 141 ms 45584 KB Output is correct
29 Correct 62 ms 12872 KB Output is correct