Submission #682729

#	Time	Username	Problem	Language	Result	Execution time	Memory
682729		urosk	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1566 ms	292352 KiB

selling_rna

#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll long long
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define sz(a) (ll)(a.size())
#define pb push_back
#define llinf 100000000000000000LL
#define endl '\n'
#define pll pair<ll,ll>
#define all(a) a.begin(),a.end()
#define fi first
#define sc second
using namespace std;
#define maxn 2000005
#define maxx 30
ll n,q;
ll t[maxn][5];
ll t2[maxn],ls[maxn],rs[maxn];
ll L[maxn],L2[maxn],R[maxn],R2[maxn];
ll root,root2,root3;
ll ti = 0,tsz = 1;
ll lid[maxn],rid[maxn];
ll in[maxn],out[maxn];
vector<ll> a[maxn];
vector<pll> v[maxn];
string ss[maxn];
map<char,ll> id;
void add(ll &v,string &s,ll i,ll d){
    if(!v) v = ++tsz;
    if(sz(s)==i||i==-1) return;
    ll c = id[s[i]];
    add(t[v][c],s,i+d,d);
}
void dfs(ll v){
    in[v] = ++ti;
    for(ll i = 0;i<4;i++){
        if(!t[v][i]) continue;
        dfs(t[v][i]);
    }
    out[v] = ti;
}
pll get(ll v,string s,ll i,ll d){
    if(sz(s)==i||i==-1) return {in[v],out[v]};
    ll c = id[s[i]];
    if(t[v][c]==0) return {-1,-2};
    return get(t[v][c],s,i+d,d);
}
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){t2[v]+=x;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,x);
    else upd(rs[v],mid+1,tr,i,x);
    t2[v] = t2[ls[v]] + t2[rs[v]];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r||tl>tr||tr<l||tl>r) return 0;
    if(tl>=l&&tr<=r) return t2[v];
    ll mid = (tl+tr)/2;
    return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
struct kv{
    ll l,r,d;
};
bool operator < (kv a,kv b){
    return a.d<b.d;
}
map<pair<pll,ll> ,ll> mp;
int main()
{
    id['A'] = 0;
    id['G'] = 1;
    id['U'] = 2;
    id['C'] = 3;
    cin >> n >> q;
    root = 1;
    root2 = 1;
    for(ll i = 1;i<=n;i++){
        string s; cin >> ss[i];
        s = ss[i];
        add(root,s,0,1);
    }
    dfs(root);
    root2 = ++tsz;
    for(ll i = 1;i<=n;i++){
        string s = ss[i];
        add(root2,s,sz(s)-1,-1);
    }
    ti = 0;
    dfs(root2);
    ll mx = tsz;
    for(ll i = 1;i<=n;i++){
        string s = ss[i];
        pll p = get(root,s,0,1);
        lid[i] = p.fi;
        p = get(root2,s,sz(s)-1,-1);
        rid[i] = p.fi;
        a[rid[i]].pb(lid[i]);
    }
    for(ll i = 1;i<=q;i++){
        string s; cin >> s;
        pll p = get(root,s,0,1);
        cin >> s;
        L[i] = p.fi,R[i] = p.sc;
        p = get(root2,s,sz(s)-1,-1);
        L2[i] = p.fi,R2[i] = p.sc;
        v[L2[i]-1].pb({L[i],R[i]});
        v[R2[i]].pb({L[i],R[i]});
    }
    tsz = root3 = 0;
    init(root3,1,mx);
    for(ll i = 0;i<=mx;i++){
        for(ll x : a[i]){
            upd(root3,1,mx,x,1);
        }
        for(pll p : v[i]){
            mp[{{p.fi,p.sc},i}] = sum(root3,1,mx,p.fi,p.sc);
        }
    }
    for(ll i = 1;i<=q;i++){
        cout<<mp[{{L[i],R[i]},R2[i]}] - mp[{{L[i],R[i]},L2[i]-1}]<<endl;
    }
}

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