oj.uz

Submission #503188

# Submission time Handle Problem Language Result Execution time Memory
503188 2022-01-07T13:08:11 Z blue Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 342 ms 253452 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8524 KB Output is correct
2 Correct 5 ms 8524 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 7 ms 8524 KB Output is correct
5 Correct 5 ms 8524 KB Output is correct
6 Correct 5 ms 8524 KB Output is correct
7 Correct 5 ms 8484 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 212616 KB Output is correct
2 Correct 237 ms 204080 KB Output is correct
3 Correct 246 ms 210756 KB Output is correct
4 Correct 237 ms 202376 KB Output is correct
5 Correct 342 ms 249788 KB Output is correct
6 Correct 316 ms 253452 KB Output is correct
7 Correct 86 ms 23744 KB Output is correct
8 Correct 224 ms 161868 KB Output is correct
9 Correct 188 ms 140024 KB Output is correct
10 Correct 155 ms 136516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18156 KB Output is correct
2 Correct 30 ms 15468 KB Output is correct
3 Correct 38 ms 17176 KB Output is correct
4 Correct 32 ms 15224 KB Output is correct
5 Correct 32 ms 15544 KB Output is correct
6 Correct 37 ms 17216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8524 KB Output is correct
2 Correct 5 ms 8524 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 7 ms 8524 KB Output is correct
5 Correct 5 ms 8524 KB Output is correct
6 Correct 5 ms 8524 KB Output is correct
7 Correct 5 ms 8484 KB Output is correct
8 Correct 243 ms 212616 KB Output is correct
9 Correct 237 ms 204080 KB Output is correct
10 Correct 246 ms 210756 KB Output is correct
11 Correct 237 ms 202376 KB Output is correct
12 Correct 342 ms 249788 KB Output is correct
13 Correct 316 ms 253452 KB Output is correct
14 Correct 86 ms 23744 KB Output is correct
15 Correct 224 ms 161868 KB Output is correct
16 Correct 188 ms 140024 KB Output is correct
17 Correct 155 ms 136516 KB Output is correct
18 Correct 44 ms 18156 KB Output is correct
19 Correct 30 ms 15468 KB Output is correct
20 Correct 38 ms 17176 KB Output is correct
21 Correct 32 ms 15224 KB Output is correct
22 Correct 32 ms 15544 KB Output is correct
23 Correct 37 ms 17216 KB Output is correct
24 Correct 231 ms 185180 KB Output is correct
25 Correct 273 ms 186296 KB Output is correct
26 Correct 237 ms 183012 KB Output is correct
27 Correct 225 ms 183172 KB Output is correct
28 Correct 210 ms 68788 KB Output is correct
29 Correct 130 ms 37312 KB Output is correct