Submission #64546

#	Time	Username	Problem	Language	Result	Execution time	Memory
64546		reality	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	824 ms	258348 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2e6 + 5;
int f[N];
void upd(int i,int h) {
    for (;i <= N;i += i&(-i))
        f[i] += h;
}
int que(int i) {
    int ans = 0;
    for (;i;i -= i&(-i))
        ans += f[i];
    return ans;
}
struct trie {
    trie * t[4];
    int pos;
    trie(void) {
        memset(t,0,sizeof(t));
        pos = -1;
    }
};
typedef trie * tr;
int g(char ch) {
    return ch == 'A' ? 0 : ch == 'U' ? 1 : ch == 'G' ? 2 : 3;
}
void add(tr root,string str) {
    auto cnt = root;
    for (auto it : str) {
        int ch = g(it);
        if (!cnt->t[ch])
            cnt->t[ch] = new trie();
        cnt = cnt->t[ch];
    }
}
void dfs(tr root,int S[],int F[],int &timer) {
    if (!root)
        return;
    root->pos = ++timer;
    S[root->pos] = timer;
    for (int i = 0;i < 4;++i)
        dfs(root->t[i],S,F,timer);
    F[root->pos] = timer;
}
int get(tr root,string str) {
    auto cnt = root;
    for (auto it : str) {
        int ch = g(it);
        cnt = cnt->t[ch];
        if (!cnt)
            break;
    }
    if (!cnt)
        return -1;
    else
        return cnt->pos;
}
tr T[2];
vi up[N];
vector < vi > qu[N];
int S[2][N];
int F[2][N];
int ans[N];
int main(void) {
    T[0] = new trie();
    T[1] = new trie();
    int n,m;
    cin>>n>>m;
    vector < string > s(n);
    for (auto & it : s) {
        cin>>it;
        add(T[0],it);
        reverse(all(it));
        add(T[1],it);
        reverse(all(it));
    }
    int timer = 0;
    dfs(T[0],S[0],F[0],timer);
    timer = 0;
    dfs(T[1],S[1],F[1],timer);
    for (auto it : s) {
        int x = get(T[0],it);
        reverse(all(it));
        int y = get(T[1],it);
        up[S[0][x]].pb(S[1][y]);
    }
    for (int i = 1;i <= m;++i) {
        string a,b;
        cin>>a>>b;
        reverse(all(b));
        int x = get(T[0],a);
        int y = get(T[1],b);
        if (x == -1 || y == -1)
            continue;
        qu[S[0][x] - 1].pb({-1,S[1][y] - 1,F[1][y],i});
        qu[F[0][x]].pb({1,S[1][y] - 1,F[1][y],i});
    }
    for (int i = 1;i < N;++i) {
        for (auto it : up[i])
            upd(it,1);
        for (auto it : qu[i])
            ans[it[3]] += it[0] * (que(it[2]) - que(it[1]));
    }
    for (int i = 1;i <= m;++i)
        cout << ans[i] << '\n';
    return 0;
}

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