oj.uz

Submission #92401

# Submission time Handle Problem Language Result Execution time Memory
92401 2019-01-02T19:20:55 Z Alexa2001 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1393 ms 1049600 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 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 44 ms 47480 KB Output is correct
2 Correct 44 ms 47480 KB Output is correct
3 Correct 44 ms 47356 KB Output is correct
4 Correct 45 ms 47480 KB Output is correct
5 Correct 44 ms 47452 KB Output is correct
6 Correct 44 ms 47396 KB Output is correct
7 Correct 43 ms 47352 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1393 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 52568 KB Output is correct
2 Correct 64 ms 51084 KB Output is correct
3 Correct 70 ms 51892 KB Output is correct
4 Correct 62 ms 50936 KB Output is correct
5 Correct 64 ms 50812 KB Output is correct
6 Correct 71 ms 51492 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 44 ms 47480 KB Output is correct
3 Correct 44 ms 47356 KB Output is correct
4 Correct 45 ms 47480 KB Output is correct
5 Correct 44 ms 47452 KB Output is correct
6 Correct 44 ms 47396 KB Output is correct
7 Correct 43 ms 47352 KB Output is correct
8 Runtime error 1393 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -