Submission #839456

#	Time	Username	Problem	Language	Result	Execution time	Memory
839456		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	249 ms	420144 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 5;
const int mod = 1e9 + 2207;
const int base = 31;
const int sqr = 1300;

int n, q;

string inp[maxn], P[maxn], Q[maxn];
pair<string, int> A[maxn];
vector<int> qq[maxn];
pair<int, int> pfxr[maxn], sfxr[maxn];

int FW[maxn], ans[maxn];

void add(int idx)
{
    for (idx; idx <= n; idx += idx & (-idx))
    {
        FW[idx]++;
    }
}

int gt(int idx)
{
    int re = 0;
    for (idx; idx > 0; idx -= idx & (-idx))
    {
        re += FW[idx];
    }
    return re;
}

int gt(char x)
{
    switch (x)
    {
    case 'A':
        return 0;
    case 'G':
        return 1;
    case 'C':
        return 2;
    case 'U':
        return 3;
    }
    return -1;
}

struct node
{
    int c[4] = {0, 0, 0, 0};
    int l = 0, r = 0;
    vector<int> rt = {};
} pfx[maxn];

int nodecnt = 0, dfscnt = 1;

void add(node &nd, string &str, int id, int pos)
{
    if (pos == str.size())
    {
        nd.rt.push_back(id);
        return;
    }
    if (!nd.c[gt(str[pos])])
    {
        nd.c[gt(str[pos])] = ++nodecnt;
        pfx[nodecnt] = node();
    }
    add(pfx[nd.c[gt(str[pos])]], str, id, pos + 1);
}

void dfs(node &nd, int ty)
{
    nd.l = dfscnt;
    for (int i = 0; i < nd.rt.size(); i++)
    {
        if (!ty)
            A[dfscnt].first = inp[nd.rt[i]];
        else
            A[nd.rt[i]].second = dfscnt;
        dfscnt++;
    }
    for (int i = 0; i < 4; i++)
    {
        if (nd.c[i])
            dfs(pfx[nd.c[i]], ty);
    }
    nd.r = dfscnt - 1;
}

pair<int, int> gtrng(node &nd, string &str, int pos)
{
    if (pos == str.size())
    {
        return {nd.l, nd.r};
    }
    if (!nd.c[gt(str[pos])])
        return {0, 0};
    return gtrng(pfx[nd.c[gt(str[pos])]], str, pos + 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> inp[i];
        add(pfx[0], inp[i], i, 0);
    }
    dfs(pfx[0], 0);
    for (int i = 1; i <= q; i++)
    {
        cin >> P[i] >> Q[i];
        pfxr[i] = gtrng(pfx[0], P[i], 0);
    }
    dfscnt = 1;
    nodecnt = 0;
    pfx[0] = node();
    for (int i = 1; i <= n; i++)
    {
        reverse(A[i].first.begin(), A[i].first.end());
        add(pfx[0], A[i].first, i, 0);
    }
    dfs(pfx[0], 1);
    for (int i = 1; i <= n; i++)
    {
        reverse(A[i].first.begin(), A[i].first.end());
        // cout << A[i].first << " " << A[i].second << "\n";
    }
    for (int i = 1; i <= q; i++)
    {
        reverse(Q[i].begin(), Q[i].end());
        sfxr[i] = gtrng(pfx[0], Q[i], 0);
        if (pfxr[i].first && sfxr[i].first)
        {
            qq[pfxr[i].first - 1].push_back(-i);
            qq[pfxr[i].second].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        add(A[i].second);
        for (auto v : qq[i])
        {
            if (v < 0)
            {
                ans[-v] += gt(sfxr[-v].first - 1);
                ans[-v] -= gt(sfxr[-v].second);
            }
            else
            {
                ans[v] -= gt(sfxr[v].first - 1);
                ans[v] += gt(sfxr[v].second);
            }
        }
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (idx; idx <= n; idx += idx & (-idx))
      |          ^~~
selling_rna.cpp: In function 'int gt(int)':
selling_rna.cpp:29:10: warning: statement has no effect [-Wunused-value]
   29 |     for (idx; idx > 0; idx -= idx & (-idx))
      |          ^~~
selling_rna.cpp: In function 'void add(node&, std::string&, int, int)':
selling_rna.cpp:63:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (pos == str.size())
      |         ~~~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(node&, int)':
selling_rna.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < nd.rt.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> gtrng(node&, std::string&, int)':
selling_rna.cpp:97:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     if (pos == str.size())
      |         ~~~~^~~~~~~~~~~~~

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