oj.uz

Submission #503187

# Submission time Handle Problem Language Result Execution time Memory
503187 2022-01-07T13:01:32 Z blue Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 248104 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;



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);
    }
};

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';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 208960 KB Output is correct
2 Correct 358 ms 200276 KB Output is correct
3 Correct 319 ms 207120 KB Output is correct
4 Correct 336 ms 198760 KB Output is correct
5 Correct 413 ms 244528 KB Output is correct
6 Correct 402 ms 248104 KB Output is correct
7 Correct 87 ms 21648 KB Output is correct
8 Correct 309 ms 160108 KB Output is correct
9 Correct 268 ms 138032 KB Output is correct
10 Correct 182 ms 132304 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 8748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 268 ms 208960 KB Output is correct
9 Correct 358 ms 200276 KB Output is correct
10 Correct 319 ms 207120 KB Output is correct
11 Correct 336 ms 198760 KB Output is correct
12 Correct 413 ms 244528 KB Output is correct
13 Correct 402 ms 248104 KB Output is correct
14 Correct 87 ms 21648 KB Output is correct
15 Correct 309 ms 160108 KB Output is correct
16 Correct 268 ms 138032 KB Output is correct
17 Correct 182 ms 132304 KB Output is correct
18 Execution timed out 1577 ms 8748 KB Time limit exceeded
19 Halted 0 ms 0 KB -