Submission #896270

#	Time	Username	Problem	Language	Result	Execution time	Memory
896270		Minhbao	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	253 ms	275064 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40