Submission #1167859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167859		dpsaveslives	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	110 ms	63776 KiB

selling_rna

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

const int MAXN = 2e6+5;
int N,M;
int ans[MAXN];
vector<pair<int,int>> pts;
vector<array<int,4>> queries;
int toval(char c){
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'U') return 2;
    if(c == 'C') return 3;
}
struct Trie{
    int trie[MAXN][4],nodes;
    int st[MAXN],num[MAXN]; //size and dfs order
    int t;
    int ins(string s){
        int pos = 0;
        for(int i = 0;i<s.size();++i){
            int c = toval(s[i]);
            if(!trie[pos][c]) trie[pos][c] = ++nodes;
            pos = trie[pos][c];
        }
        return pos;
    }
    int finden(string s){
        int pos = 0;
        for(int i = 0;i<s.size();++i){
            int c = toval(s[i]);
            if(!trie[pos][c]) return -1;
            pos = trie[pos][c];
        }
        return pos;
    }
    void dfs(int u){
        num[u] = t++;
        st[u] = 1;
        for(int i = 0;i<=3;++i){
            if(trie[u][i]){
                dfs(trie[u][i]);
                st[u] += st[trie[u][i]];
            }
        }
    }
}pref, suf;
struct BIT{
    int tree[MAXN];
    void upd(int pos, int val){
        ++pos;
        for(;pos < MAXN;pos += (pos&(-pos))){
            tree[pos] += val;
        }
    }
    int query(int pos){
        ++pos; int ret = 0;
        while(pos > 0){
            ret += tree[pos];
            pos -= (pos&(-pos));
        }
        return ret;
    }
}bit;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 1;i<=N;++i){
        string s; cin >> s;
        int ind1 = pref.ins(s);
        reverse(s.begin(),s.end());
        int ind2 = suf.ins(s);
        pts.push_back({ind1,ind2});
    }
    pref.t = suf.t = 0;
    pref.dfs(0); suf.dfs(0);
    for(int i = 0;i<pts.size();++i){
        pts[i].ff = pref.num[pts[i].ff];
        pts[i].ss = suf.num[pts[i].ss];
    }
    for(int i = 1;i<=M;++i){
        string pref1, suf1; cin >> pref1 >> suf1;
        reverse(suf1.begin(),suf1.end());
        int u = pref.finden(pref1), v = suf.finden(suf1);
        if(u == -1 || v == -1) ans[i] = 0;
        else{
            int pref2 = pref.num[u], suf2 = suf.num[v];
            int szp = pref.st[u], szs = suf.st[v];
            queries.push_back({pref2-1,suf2-1,i,1});
            queries.push_back({pref2-1,suf2+suf.st[v]-1,i,-1});
            queries.push_back({pref2+pref.st[u]-1,suf2-1,i,-1});
            queries.push_back({pref2+pref.st[u]-1,suf2+suf.st[v]-1,i,1});
        }
    }
    sort(pts.begin(),pts.end()); sort(queries.begin(),queries.end());
    int P = pts.size(), Q = queries.size();
    int pi = 0, qi = 0, nodes = pref.nodes;
    //cout << P << " " << Q << "\n";
    for(int i = 0;i<=nodes;++i){
        while(pi < P){
            int x = pts[pi].ff, y = pts[pi].ss;
            if(x != i) break;
            bit.upd(y,1);
            ++pi;
        }
        while(qi < Q){
            int x = queries[qi][0], y = queries[qi][1], ind = queries[qi][2], w = queries[qi][3];
            if(x != i) break;
            int tmp = bit.query(y);
            ans[ind] += w*tmp;
            ++qi;
        }
    }
    for(int i = 1;i<=M;++i){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int toval(char)':
selling_rna.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

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