Submission #682897

#	Time	Username	Problem	Language	Result	Execution time	Memory
682897		urosk	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	605 ms	709348 KiB

selling_rna

#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll int
#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 8000005
#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;
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);
}
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
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 = 0;
    FenwickTree f(mx);
    for(ll i = 0;i<=mx;i++){
        for(ll x : a[i]){
            f.add(x,1);
        }
        for(pll p : v[i]){
            mp[{{p.fi,p.sc},i}] = f.sum(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: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40