Submission #503188

#	Time	Username	Problem	Language	Result	Execution time	Memory
503188		blue	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	342 ms	253452 KiB

selling_rna

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define sz(x) int(x.size())
using vi = vector<int>;
using pii = pair<int, int>;
const int INF = 1'000'000'00;
const int lim = 100'000;



int fwd_ct = 0;
vi fwd_act_ind(1+100'000);

int bwd_ct = 0;
vi bwd_act_ind(1+100'000);

struct trie
{
    vi occ;
    vi trav;

    trie* child[4] = {NULL, NULL, NULL, NULL};

    // int lo = INF;
    // int hi = -INF;
    pii rng{INF, -INF}; //lo, hi

    void insert(int i, vi& s, int l)
    {
        if(l == sz(s)) occ.push_back(i);
        else
        {
            if(child[s[l]] == NULL) child[s[l]] = new trie;
            child[s[l]]->insert(i, s, l+1);
        }
    }

    void traverse(int& ct, vi& act_ind)
    {
        // cerr << "t enter\n";
        for(int i = 0; i < sz(occ); i++)
        {
            // cerr << "i = " << i << '\n';

            trav.push_back(++ct);
            // cerr << "pushed\n";
            act_ind[occ[i]] = trav[i];
            // cerr <<"done\n";
        }

        for(int y = 0; y < 4; y++)
            if(child[y] != NULL)
                child[y]->traverse(ct, act_ind);
        // cerr << "t exit\n";
    }

    pii compute_ind()
    {
        if(!trav.empty())
        {
            rng.first = trav[0];
            rng.second = trav.back();
        }
        for(int y = 0; y < 4; y++)
        {
            if(child[y] != NULL)
            {
                pii z = child[y]->compute_ind();
                rng.first = min(rng.first, z.first);
                rng.second = max(rng.second, z.second);
            }
        }
        return rng;
    }

    pii locate(vi& s, int l)
    {
        if(l == sz(s)) return rng;
        else if(child[s[l]] == NULL) return {INF, -INF};
        else return child[s[l]]->locate(s, l+1);
    }
};

vi BIT(1+lim);

void incr(int a)
{
    for(int y = a; y <= lim; y += y&-y)
        BIT[y]++;
}

int prefsum(int a)
{
    int r = 0;
    for(int y = a; y >= 1; y -= y&-y)
        r += BIT[y];
    return r;
}

int rangesum(int a, int b)
{
    return prefsum(b) - prefsum(a-1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vi act(1000, -1);
    act['A'] = 0;
    act['C'] = 1;
    act['G'] = 2;
    act['U'] = 3;

    int N, M;
    cin >> N >> M;

    trie FWD, BWD;

    vi S[1+N], S_rev[1+N];
    for(int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        for(char c: s) S[i].push_back(act[c]);
        S_rev[i] = S[i];
        reverse(S_rev[i].begin(), S_rev[i].end());

        FWD.insert(i, S[i], 0);
        BWD.insert(i, S_rev[i], 0);
    }
    // cerr << "X\n";

    FWD.traverse(fwd_ct, fwd_act_ind);
    BWD.traverse(bwd_ct, bwd_act_ind);

    // cerr << "Y\n";

    FWD.compute_ind();
    BWD.compute_ind();
    //
    // cerr << "Z\n";
    //
    // for(int i = 1; i <= N; i++)
    // {
    //     cerr << i << " : ";
    //     for(int q = 0; q < sz(S[i]); q++) cerr << S[i][q];
    //     cerr << " : " << fwd_act_ind[i] << ' ' << bwd_act_ind[i] << '\n';
    // }
    //


    // cerr << "\n\n\n\n\n";


    vi f1(1+M), f2(1+M), b1(1+M), b2(1+M);

    for(int j = 1; j <= M; j++)
    {
        string p, q;
        cin >> p >> q;

        vi P, Q;
        for(char p1: p) P.push_back(act[p1]);

        for(char q1: q) Q.push_back(act[q1]);

        reverse(Q.begin(), Q.end());

        pii f = FWD.locate(P, 0);
        pii b = BWD.locate(Q, 0);

        f1[j] = f.first;
        f2[j] = f.second;
        b1[j] = b.first;
        b2[j] = b.second;

        // int ans = 0;

        // for(int i = 1; i <= N; i++)
        // {
        //     if(f1[j] <= fwd_act_ind[i] && fwd_act_ind[i] <= f2[j])
        //         if(b1[j] <= bwd_act_ind[i] && bwd_act_ind[i] <= b2[j])
        //             ans++;
        // }
        // cout << ans << '\n';
    }

    vi res(1+M, 0);


    vi f1_occ[1+lim];
    vi str_occ[1+lim];
    vi f2_occ[1+lim];
    for(int j = 1; j <= M; j++)
    {
        if(f1[j] == INF || b1[j] == INF) continue;
        f1_occ[f1[j]].push_back(j);
        f2_occ[f2[j]].push_back(j);
    }
    for(int i = 1; i <= N; i++) str_occ[fwd_act_ind[i]].push_back(i);


    for(int w = 1; w <= lim; w++)
    {
        for(int j: f1_occ[w])
            res[j] -= rangesum(b1[j], b2[j]);

        for(int i: str_occ[w])
            incr(bwd_act_ind[i]);

        for(int j: f2_occ[w])
            res[j] += rangesum(b1[j], b2[j]);
    }

    for(int j = 1; j <= M; j++) cout << res[j] << '\n';
}

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