oj.uz

Submission #92402

# Submission time Handle Problem Language Result Execution time Memory
92402 2019-01-02T19:22:38 Z Alexa2001 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 336 ms 161528 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e6 + 5;

struct segment
{
    int x, y;
};
struct query
{
    segment s; int id;
};
map<char, int> code;
vector<query> queries[Nmax];
vector<int> v[Nmax];

int pref[Nmax], suff[Nmax], n, ans[Nmax];
char *s[Nmax], A[Nmax], B[Nmax], S[Nmax];

struct Trie
{
    int n, tmp;
    int nxt[Nmax][4], in[Nmax], out[Nmax];

    void add(char *s, int node = 0)
    {
        if(!s[0]) return;
        int go = code[s[0]];

        if(!nxt[node][go]) nxt[node][go] = ++n;
        add(s+1, nxt[node][go]);
    }

    int search_pos(char *s, int node = 0)
    {
        if(!s[0]) return node;
        int go = code[s[0]];

        if(!nxt[node][go]) return -1;
        return search_pos(s+1, nxt[node][go]);
    }

    void dfs(int node = 0)
    {
        int i;
        in[node] = ++tmp;
        for(i=0; i<4; ++i)
            if(nxt[node][i]) dfs(nxt[node][i]);
        out[node] = tmp;
    }

    segment search_subarb(char *s)
    {
        int node = search_pos(s);
        if(node == -1) return {-1, -1};
        return {in[node], out[node]};
    }
} one, two;


struct AIB
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }
public:
    void update(int pos)
    {
        for(; pos <= two.tmp; pos += ub(pos)) ++a[pos];
    }

    int query(segment K)
    {
        int x = K.x, y = K.y;
        int ans = 0;
        for(; y; y-=ub(y)) ans += a[y];
        for(--x; x; x-=ub(x)) ans -= a[x];
        return ans;
    }
} aib;


void precalc()
{
    int i;
    for(i=1; i<=n; ++i) one.add(s[i]);
    one.dfs();

    for(i=1; i<=n; ++i)
        pref[i] = one.search_pos(s[i]);

    for(i=1; i<=n; ++i)
    {
        int L = strlen(s[i]);
        reverse(s[i], s[i] + L);
        two.add(s[i]);
    }
    two.dfs();

    for(i=1; i<=n; ++i)
        suff[i] = two.search_pos(s[i]);

    for(i=1; i<=n; ++i)
        v[one.in[pref[i]]].push_back(two.in[suff[i]]);
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    code['A'] = 0; code['G'] = 1; code['C'] = 2; code['U'] = 3;

    int i, q;
    scanf("%d %d\n", &n, &q);
    for(i=1; i<=n; ++i)
    {
        scanf("%s\n", S);
        int L = strlen(S);
        s[i] = new char [L + 1];
        memcpy(s[i], S, L);
    }

    precalc();

    for(i=1; i<=q; ++i)
    {
        scanf("%s %s\n", A, B);
        int L = strlen(B);
        reverse(B, B+L);

        segment before, after;
        before = one.search_subarb(A);
        after = two.search_subarb(B);

        if(before.x == -1 || after.x == -1) continue;

        queries[before.x - 1].push_back({after, -i});
        queries[before.y].push_back({after, i});
    }

    for(i=1; i<=one.tmp; ++i)
    {
        for(auto it : v[i]) aib.update(it);
        for(auto it : queries[i])
        {
            int res = aib.query(it.s);
            if(it.id > 0) ans[it.id] += res;
                else ans[-it.id] -= res;
        }
    }

    for(i=1; i<=q; ++i) printf("%d\n", ans[i]);
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s\n", S);
         ~~~~~^~~~~~~~~~~
selling_rna.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %s\n", A, B);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94328 KB Output is correct
2 Correct 75 ms 94456 KB Output is correct
3 Correct 74 ms 94448 KB Output is correct
4 Correct 89 ms 94456 KB Output is correct
5 Correct 88 ms 94456 KB Output is correct
6 Correct 86 ms 94456 KB Output is correct
7 Correct 86 ms 94456 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 153184 KB Output is correct
2 Correct 268 ms 151748 KB Output is correct
3 Correct 284 ms 146552 KB Output is correct
4 Correct 260 ms 144248 KB Output is correct
5 Correct 336 ms 160604 KB Output is correct
6 Correct 335 ms 161528 KB Output is correct
7 Correct 138 ms 101752 KB Output is correct
8 Correct 227 ms 139236 KB Output is correct
9 Correct 204 ms 133204 KB Output is correct
10 Correct 177 ms 129756 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 99032 KB Output is correct
2 Correct 103 ms 97544 KB Output is correct
3 Correct 108 ms 98608 KB Output is correct
4 Correct 92 ms 97528 KB Output is correct
5 Correct 96 ms 97272 KB Output is correct
6 Correct 111 ms 98040 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94328 KB Output is correct
2 Correct 75 ms 94456 KB Output is correct
3 Correct 74 ms 94448 KB Output is correct
4 Correct 89 ms 94456 KB Output is correct
5 Correct 88 ms 94456 KB Output is correct
6 Correct 86 ms 94456 KB Output is correct
7 Correct 86 ms 94456 KB Output is correct
8 Correct 301 ms 153184 KB Output is correct
9 Correct 268 ms 151748 KB Output is correct
10 Correct 284 ms 146552 KB Output is correct
11 Correct 260 ms 144248 KB Output is correct
12 Correct 336 ms 160604 KB Output is correct
13 Correct 335 ms 161528 KB Output is correct
14 Correct 138 ms 101752 KB Output is correct
15 Correct 227 ms 139236 KB Output is correct
16 Correct 204 ms 133204 KB Output is correct
17 Correct 177 ms 129756 KB Output is correct
18 Correct 97 ms 99032 KB Output is correct
19 Correct 103 ms 97544 KB Output is correct
20 Correct 108 ms 98608 KB Output is correct
21 Correct 92 ms 97528 KB Output is correct
22 Correct 96 ms 97272 KB Output is correct
23 Correct 111 ms 98040 KB Output is correct
24 Correct 235 ms 145952 KB Output is correct
25 Correct 233 ms 147320 KB Output is correct
26 Correct 213 ms 144888 KB Output is correct
27 Correct 228 ms 139036 KB Output is correct
28 Correct 234 ms 115576 KB Output is correct
29 Correct 169 ms 106744 KB Output is correct