Submission #1025139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025139		_8_8_	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	662 ms	687052 KiB

selling_rna

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 2e5 + 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;
}

struct bit{
    vector<int> t;
    int n;
    void init(int s){
        n = s;
        t.assign((s + 1) * 4,0);
    }
    void upd(int pos,int val,int v,int tl,int tr){
        t[v] += val;
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,v+v,tl,tm);
        else upd(pos,val,v+v+1,tm+1,tr);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(l > r || tl >r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
};

vector<int> f[N],t[N * 4];
bit b[N * 4];
int mx;
void build(int v = 1,int tl = 1,int tr = mx){
    if(tl == tr){
        t[v] = f[tl];
        t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
        b[v].init((int)t[v].size());
    }else{
        int tm = (tl + tr) >> 1;
        build(v+v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
        merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
        t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
        b[v].init((int)t[v].size());
    }
}
void upd(int x,int y,int v = 1,int tl = 1,int tr = mx){
    int it = lower_bound(t[v].begin(),t[v].end(),y) - t[v].begin() + 1;
    b[v].upd(it,1,1,1,b[v].n);
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    if(x <= tm) upd(x,y,v+v,tl,tm);
    else upd(x,y,v+v+1,tm+1,tr);
}
int res = 0;
int get(int l,int r,int l1,int r1,int v = 1,int tl = 1,int tr = mx){
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r){
        int it = lower_bound(t[v].begin(),t[v].end(),l1) - t[v].begin() + 1;
        int it1 = upper_bound(t[v].begin(),t[v].end(),r1) - t[v].begin();
        return b[v].get(it,it1,1,1,b[v].n);
    }else{
        int tm = (tl + tr) >> 1;
        return get(l,r,l1,r1,v+v,tl,tm) + get(l,r,l1,r1,v+v+1,tm+1,tr);
    }
}
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);
    mx= (int)c.size() + 1;
    for(int i = 1;i <= n;i++){
        pt[i][0] = find(c,pt[i][0]);
        pt[i][1] = find(c1,pt[i][1]);
        f[pt[i][0]].push_back(pt[i][1]);
    }
    build();
    for(int i = 1;i <= n;i++){
        // cout << pt[i][0] << ' ' << pt[i][1] << '\n';
        upd(pt[i][0],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);
        cout << get(ti.first,ti.second,to.first,to.second)  << '\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: 25 / 25
• Subtask 4: 40 / 40