Submission #1025110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025110		_8_8_	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1531 ms	641876 KiB

selling_rna

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 3e5 + 20, MOD = (int)1e9+7;

struct node{
    node *next[26];
    int tin,tout;
    vector<int> id;
    node(){
        tin = 0,tout = 0;
        for(int i = 0;i < 26;i++){
            next[i] = nullptr;
        }
    }
};
 
node *p = new node(),*s = new node();
using pnode = node *;
int sp = 0,ss = 0;
int n,q;
void add(pnode v,string &x,int j){
    for(int i = 0;i < (int)x.size();i++){
        if(!v->next[(x[i] - 'A')]){
            v->next[(x[i] - 'A')] = new node();
        }
        v = v->next[(x[i] - 'A')];
    }
    v->id.push_back(j);
}
int timer = 0;
array<int,2> pt[N];
vector<int> c,c1;
void dfs(pnode v){
    v->tin = ++timer;
    for(int k:v->id){
        if(pt[k][0] == -1){
            pt[k][0] = timer;
            c.push_back(timer);
        }else{
            pt[k][1] = timer;
            c1.push_back(timer);
        }
    }
    for(int t = 0;t < 26;t++){
        if(v->next[t]){
            dfs(v->next[t]);
        }
    }
    v->tout = ++timer;
}
pair<int,int> get_tin(pnode v,string &x){
    for(int i = 0;i < (int)x.size();i++){
        if(v->next[(x[i] - 'A')]){
            v = v->next[(x[i] - 'A')];
        }else return {-1,-1};
    }
    return {v->tin,v->tout};
}
void make(vector<int> &x){
    sort(x.begin(),x.end());
    x.resize(unique(x.begin(),x.end()) - x.begin());
}
string X[N],Y[N];
int find(vector<int> &x,int a){
    int it = lower_bound(x.begin(),x.end(),a) - x.begin();
    return it + 1;
}
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        string t;
        cin >> t;
        add(p,t,i);
        reverse(t.begin(),t.end());
        add(s,t,i);
        pt[i] = {-1,-1};
    }
    dfs(p);
    timer = 0;
    dfs(s);
    for(int i = 0;i < q;i++){
        string x,y;
        cin >> x >> y;
        reverse(y.begin(),y.end());
        X[i] = x;
        Y[i] = y;
        pair<int,int> ti = get_tin(p,x),to = get_tin(s,y);
        c.push_back(ti.first);
        c.push_back(ti.second);
        c1.push_back(to.first);
        c1.push_back(to.second);
    }
    make(c);
    make(c1);
    for(int i = 1;i <= n;i++){
        pt[i][0] = find(c,pt[i][0]);
        pt[i][1] = find(c1,pt[i][1]);
    }
    for(int i = 0;i < q;i++){
        pair<int,int> ti = get_tin(p,X[i]),to = get_tin(s,Y[i]);
        ti.first = find(c,ti.first);
        ti.second = find(c,ti.second);
        to.first = find(c1,to.first);
        to.second = find(c1,to.second);
        int res = 0;
        for(int j = 1;j <= n;j++){
            if(pt[j][0] >= ti.first && pt[j][0] <= ti.second && pt[j][1] >=to.first && pt[j][1] <= to.second){
                res++;
            }
        }
        cout << res << '\n';

    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40