Submission #1181587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181587		vnedu	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	100 ms	68388 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "RNA"

/// end of template ///

const int N = 1e5 + 15;
const int M = 2e6 + 26;

struct Query {
    int x,b,t,xxx,id;
    Query() {}
    Query(int x, int b, int t, int xxx, int id) : x(x), b(b), t(t), xxx(xxx), id(id) {}

    bool operator < (const Query &S) const {
        return x<S.x;
    }
};

char mp[26];
int numString,numQuery,ptr=1,bit[M*2],dp[N];
ii point[N];
vector<Query> v;

void add(int x, int val) {
//    cout<<x<<'\n';
//    return;
    while (x<M*2) {
        bit[x]+=val;
        x+=x&-x;
    }
}

int get(int x) {
    int ans=0;
    while (x>=1) {
        ans+=bit[x];
        x-=x&-x;
    } return ans;
}

struct trie {
    int tg,tr[M][4],st[M],en[M];
    trie() {tg=1;}

    int add(string s) {
        int u=1;
        for (char ch : s) {
            int nxt=mp[ch-'A'];
            if (tr[u][nxt]==0) tr[u][nxt]=++tg;
            u=tr[u][nxt];
        } return u;
    }

    void dfs(int u, int pa) {
        st[u]=++tg;
        for (int i=0; i<4; ++i) {
            int v=tr[u][i];
            if (v!=0) dfs(v,u);
        }

        en[u]=++tg;
    }

    void work() {
        tg=0; dfs(1,-1);
    }

} pre,suf;

void solve() {
    mp['G'-'A']=0;
    mp['U'-'A']=1;
    mp['A'-'A']=2;
    mp['C'-'A']=3;

    cin>>numString>>numQuery;
    for (int i=1; i<=numString; ++i) {
        string s; cin>>s;
        point[i].se=pre.add(s);
        reverse(all(s));
        point[i].fi=suf.add(s);
//        cout<<point[i].fi<<' '<<point[i].se<<'\n';
    } pre.work(); suf.work();

    for (int i=1; i<=numString; ++i) point[i].se=pre.st[point[i].se],point[i].fi=suf.st[point[i].fi];
//    for (int i=1; i<=numString; ++i) if (min(point[i].fi,point[i].se)==0) cout<<i<<' '<<point[i].fi<<' '<<point[i].se<<'\n';
    for (int i=1; i<=numQuery; ++i) {
        string s,t; cin>>s>>t; reverse(all(t));
        int us=1;
        bool is=1;

        for (char ch : s) {
            us=pre.tr[us][mp[ch-'A']];
            if (us==0) {
                is=0;
                break;
            }
        }

        int ut=1;
        for (char ch : t) {
            ut=suf.tr[ut][mp[ch-'A']];
            if (ut==0) {
                is=0;
                break;
            }
        }

        if (is==0) continue;
        int b=pre.st[us],top=pre.en[us],l=suf.st[ut],r=suf.en[ut];
        v.pb(Query(r,b,top,1,i));
        v.pb(Query(l-1,b,top,-1,i));
    }

    sort(all(v));
    sort(point+1,point+1+numString);
    for (Query &cm : v) {
        while (point[ptr].fi<=cm.x && ptr<=numString) add(point[ptr].se,1),++ptr;
        dp[cm.id]+=cm.xxx*(get(cm.t)-get(cm.b-1));
    }

    for (int i=1; i<=numQuery; ++i) cout<<dp[i]<<'\n';
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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