Submission #1150206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150206		dosts	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1104 ms	1070004 KiB

selling_rna

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 2e6+1,MOD = 1e9+7,BL = 1000;

vi ans(N);

struct Node {
    vector<pair<string,int>> Queries;
    string str;
    int bas = 0;
    vi star;
    int c[26]{};
};

Node clean;

struct Trie {
    vector<Node> nds = {clean};
    int ctr = 0;
    void parent(int node,int p,int id) {
        nds[p].c[id] = node;
    }
    void insert(int node, string& s,int ptr,int t) {
        nds[node].star.push_back(t);
        if (ptr == s.size()) {
            nds[node].bas++;
            if (nds[node].str.empty()) {
                nds[node].str = s;
                reverse(all(nds[node].str));
            }
            return;
        }
        if (!nds[node].c[s[ptr]-'A']) {
            nds.push_back(clean);
            parent(++ctr,node,s[ptr]-'A');
        }
        ptr++;
        insert(nds[node].c[s[ptr-1]-'A'],s,ptr,t);
    }

    void insertquery(int node,string& s,string& t,int qid,int ptr) {
        if (ptr == s.size()) {
            nds[node].Queries.push_back({t,qid});
            return;
        }
        if (!nds[node].c[s[ptr]-'A']) {
            nds.push_back(clean);
            parent(++ctr,node,s[ptr]-'A');
        }
        ptr++;
        insertquery(nds[node].c[s[ptr-1]-'A'],s,t,qid,ptr);
    }

    int ask(int node,string& s,int ptr) {
        if (ptr == s.size()) return node;
        if (!nds[node].c[s[ptr]-'A']) return -1;
        ptr++;
        return ask(nds[node].c[s[ptr-1]-'A'],s,ptr);
    }
} trie,trie2;


int idx(vi& v,int x) {
    return upper_bound(all(v),x)-v.begin();
}
vi tin(N);
int timer = 0;
void walk(int node) {
    tin[node] = timer++;
    Node& nd = trie.nds[node];
    //cout << "NODE" sp node sp nd.star.size() sp nd.Queries.size() << endl;
    for (int i = 0;i<26;i++) if (nd.c[i]) walk(nd.c[i]);
    if (!nd.str.empty()) for (int i = 0;i<nd.bas;i++) {
        //cout << "INSERTING" sp nd.str sp tin[node] << endl;
        trie2.insert(0,nd.str,0,tin[node]);
    }
    for (auto Q : nd.Queries) {
        int tnode = trie2.ask(0,Q.ff,0);
        if (tnode == -1) ans[Q.ss] = 0;
        else ans[Q.ss] = trie2.nds[tnode].star.size()-idx(trie2.nds[tnode].star,tin[node]-1);
        //cout << "ASKING" sp Q.ff sp tin[node] sp tnode sp  ans[Q.ss] << '\n';
    }
}
void solve() { 
    int n,q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) {
        string s;
        cin >> s;
        trie.insert(0,s,0,0);
    }
    for (int i=1;i<=q;i++) {
        string pref,suf;
        cin >> pref >> suf;
        reverse(all(suf));
        trie.insertquery(0,pref,suf,i,0);
    } 
    walk(0);
    for (int i=1;i<=q;i++) cout << ans[i] << '\n'; 
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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