Submission #361768

#	Time	Username	Problem	Language	Result	Execution time	Memory
361768		RyoPham	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	884 ms	474604 KiB

selling_rna

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2e6 + 5;

int n, m;
string s[maxn], t[maxn];
int s_id[maxn], t_id[maxn];

string q_pref[maxn], q_suff[maxn];
int q_pref_id[maxn], q_suff_id[maxn];

int nnode[2];
int gr[2][maxn][4];

int ntime;
int tin[2][maxn], tout[2][maxn];

struct fenwick
{
    vector<int> vals[maxn], sum[maxn];

    void fake_update(int x, int y)
    {
        for(; x < maxn; x += x & -x)
            vals[x].push_back(y);
    }

    void fake_get(int x, int y)
    {
        for(; x > 0; x -= x & -x)
            vals[x].push_back(y);
    }

    void fake_get(int xl, int yl, int xr, int yr)
    {
        fake_get(xr, yr);
        fake_get(xl - 1, yr);
        fake_get(xr, yl - 1);
        fake_get(xl - 1, yl - 1);
    }

    void modify()
    {
        for(int x = 1; x < maxn; ++x)
        {
            sort(vals[x].begin(), vals[x].end());
            vals[x].erase(unique(vals[x].begin(), vals[x].end()), vals[x].end());
            sum[x].assign(sz(vals[x]) + 1, 0);
        }
    }

    void update(int x, int yy)
    {
        for(; x < maxn; x += x & -x)
            for(int y = lower_bound(vals[x].begin(), vals[x].end(), yy) - vals[x].begin() + 1; y <= sz(vals[x]); y += y & -y)
                ++sum[x][y];
    }

    int get(int x, int yy)
    {
        int res = 0;
        for(; x > 0; x -= x & -x)
            for(int y = lower_bound(vals[x].begin(), vals[x].end(), yy) - vals[x].begin() + 1; y > 0; y -= y & -y)
                res += sum[x][y];
        return res;
    }

    int get(int xl, int yl, int xr, int yr)
    {
        return get(xr, yr) - get(xl - 1, yr) - get(xr, yl - 1) + get(xl - 1, yl - 1);
    }
} tree;

int get_type(char c)
{
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    if(c == 'U') return 3;
    return -1;
}

void read_input()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        t[i] = s[i];
        reverse(t[i].begin(), t[i].end());
    }
    for(int i = 1; i <= m; ++i)
    {
        cin >> q_pref[i] >> q_suff[i];
        reverse(q_suff[i].begin(), q_suff[i].end());
    }
}

int add(int id, string s)
{
    int cur = 1;
    for(int i = 0; i < sz(s); ++i)
    {
        int nxt = gr[id][cur][get_type(s[i])];
        if(nxt == 0)
            nxt = gr[id][cur][get_type(s[i])] = ++nnode[id];
        cur = nxt;
    }
    return cur;
}

int dfs_find(int id, string s)
{
    int cur = 1;
    for(int i = 0; i < sz(s); ++i)
    {
        int nxt = gr[id][cur][get_type(s[i])];
        if(nxt == 0)
            return 0;
        cur = nxt;
    }
    return cur;
}

void dfs(int id, int u)
{
    tin[id][u] = ++ntime;
    for(int k = 0; k < 4; ++k)
        if(gr[id][u][k]) dfs(id, gr[id][u][k]);
    tout[id][u] = ntime;
}

void init()
{
    nnode[0] = nnode[1] = 1;
    for(int i = 1; i <= n; ++i)
    {
        s_id[i] = add(0, s[i]);
        t_id[i] = add(1, t[i]);
    }
    for(int i = 1; i <= m; ++i)
    {
        q_pref_id[i] = dfs_find(0, q_pref[i]);
        q_suff_id[i] = dfs_find(1, q_suff[i]);
    }
    for(int i = 0; i < 2; ++i)
    {
        ntime = 0;
        dfs(i, 1);
    }
    for(int i = 1; i <= n; ++i)
        tree.fake_update(tin[0][s_id[i]], tin[1][t_id[i]]);
    for(int i = 1; i <= m; ++i)
        if(q_pref_id[i] && q_suff_id[i])
            tree.fake_get(tin[0][q_pref_id[i]], tin[1][q_suff_id[i]], tout[0][q_pref_id[i]], tout[1][q_suff_id[i]]);
    tree.modify();
}

void solve()
{
    for(int i = 1; i <= n; ++i)
        tree.update(tin[0][s_id[i]], tin[1][t_id[i]]);
    for(int i = 1; i <= m; ++i)
        cout << (q_pref_id[i] && q_suff_id[i] ?
                 tree.get(tin[0][q_pref_id[i]], tin[1][q_suff_id[i]], tout[0][q_pref_id[i]], tout[1][q_suff_id[i]]) : 0) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

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