oj.uz

Submission #361768

# Submission time Handle Problem Language Result Execution time Memory
361768 2021-01-31T15:01:21 Z RyoPham Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 884 ms 474604 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 407644 KB Output is correct
2 Correct 325 ms 407628 KB Output is correct
3 Correct 326 ms 407660 KB Output is correct
4 Correct 328 ms 407532 KB Output is correct
5 Correct 325 ms 407532 KB Output is correct
6 Correct 326 ms 407532 KB Output is correct
7 Correct 326 ms 407532 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 464876 KB Output is correct
2 Correct 484 ms 463212 KB Output is correct
3 Correct 524 ms 465644 KB Output is correct
4 Correct 505 ms 463680 KB Output is correct
5 Correct 561 ms 473708 KB Output is correct
6 Correct 564 ms 474604 KB Output is correct
7 Correct 399 ms 421100 KB Output is correct
8 Correct 483 ms 457452 KB Output is correct
9 Correct 476 ms 451820 KB Output is correct
10 Correct 439 ms 445420 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 414736 KB Output is correct
2 Correct 447 ms 413540 KB Output is correct
3 Correct 466 ms 414796 KB Output is correct
4 Correct 399 ms 412848 KB Output is correct
5 Correct 432 ms 413792 KB Output is correct
6 Correct 461 ms 415180 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 407644 KB Output is correct
2 Correct 325 ms 407628 KB Output is correct
3 Correct 326 ms 407660 KB Output is correct
4 Correct 328 ms 407532 KB Output is correct
5 Correct 325 ms 407532 KB Output is correct
6 Correct 326 ms 407532 KB Output is correct
7 Correct 326 ms 407532 KB Output is correct
8 Correct 485 ms 464876 KB Output is correct
9 Correct 484 ms 463212 KB Output is correct
10 Correct 524 ms 465644 KB Output is correct
11 Correct 505 ms 463680 KB Output is correct
12 Correct 561 ms 473708 KB Output is correct
13 Correct 564 ms 474604 KB Output is correct
14 Correct 399 ms 421100 KB Output is correct
15 Correct 483 ms 457452 KB Output is correct
16 Correct 476 ms 451820 KB Output is correct
17 Correct 439 ms 445420 KB Output is correct
18 Correct 418 ms 414736 KB Output is correct
19 Correct 447 ms 413540 KB Output is correct
20 Correct 466 ms 414796 KB Output is correct
21 Correct 399 ms 412848 KB Output is correct
22 Correct 432 ms 413792 KB Output is correct
23 Correct 461 ms 415180 KB Output is correct
24 Correct 541 ms 460264 KB Output is correct
25 Correct 629 ms 464084 KB Output is correct
26 Correct 507 ms 458252 KB Output is correct
27 Correct 576 ms 461416 KB Output is correct
28 Correct 884 ms 444844 KB Output is correct
29 Correct 645 ms 426764 KB Output is correct