oj.uz

Submission #241579

# Submission time Handle Problem Language Result Execution time Memory
241579 2020-06-24T14:25:01 Z AM1648 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 182 ms 79352 KB 
/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 100010;
const ll maxm = 2000010;

ll n, Q, nn;
vi T[maxn], P[maxn], S[maxn];
ll mapp[128];
ll trie[maxm][4], node[maxn];
ll st[maxm], ft[maxm], cnt[maxm];
pii stnode[maxn];
ll res[maxn];
vpii qs[maxn];

void inp(vi &o) {
    string s; cin >> s;
    o.resize(s.size());
    fori (i, s.size()) {
        o[i] = mapp[s[i]];
    }
}

ll tim = 0;
void dfs(ll x) {
    st[x] = tim++;
    fori (i, 4) if (trie[x][i]) {
        dfs(trie[x][i]);
    }
    ft[x] = tim;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

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

    cin >> n >> Q;
    fori (i, n) inp(T[i]);
    fori (i, Q) {
        inp(P[i]);
        inp(S[i]);
    }
    nn = 1;
    fori (i, n) {
        ll x = 0;
        for (auto c : T[i]) {
            if (!trie[x][c]) trie[x][c] = nn++;
            x = trie[x][c];
        }
        node[i] = x;
    }
    dfs(0);
    fori (i, n) {
        stnode[i] = {st[node[i]], i};
    }
    sort(stnode, stnode + n);
    fori (i, Q) {
        ll x = 0;
        for (auto c : P[i]) {
            if (!trie[x][c]) {
                x = -1;
                break;
            }
            x = trie[x][c];
        }
        if (x != -1) {
            ll stid = lower_bound(stnode, stnode + n, make_pair(st[x], -1)) - stnode;
            ll ftid = lower_bound(stnode, stnode + n, make_pair(ft[x], -1)) - stnode;
            qs[stid].eb(i, -1);
            qs[ftid].eb(i, 1);
        }
    }
    nn = 1;
    memset(trie, 0, sizeof trie);
    fori (i, Q) reverse(all(S[i]));
    fori (i, n) reverse(all(T[i]));
    fori (i, n + 1) {
        for (auto q : qs[i]) {
            ll x = 0;
            for (auto c : S[q.F]) {
                if (!trie[x][c]) {
                    x = -1;
                    break;
                }
                x = trie[x][c];
            }
            if (x != -1) res[q.F] += cnt[x] * q.S;
        }
        if (i == n) break;
        ll x = 0;
        ll ti = stnode[i].S;
        for (auto c : T[ti]) {
            if (!trie[x][c]) trie[x][c] = nn++;
            x = trie[x][c];
            ++cnt[x];
        }
    }
    fori (i, Q) cout << res[i] << '\n';

}

Compilation message

selling_rna.cpp: In function 'void inp(vi&)':
selling_rna.cpp:26:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forifrom(i, s, n) for (ll i = s; i < n; ++i)
                                            ^
selling_rna.cpp:28:20: note: in expansion of macro 'forifrom'
 #define fori(i, n) forifrom (i, 0, n)
                    ^~~~~~~~
selling_rna.cpp:73:5: note: in expansion of macro 'fori'
     fori (i, s.size()) {
     ^~~~
selling_rna.cpp:74:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         o[i] = mapp[s[i]];
                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41088 KB Output is correct
2 Correct 27 ms 41088 KB Output is correct
3 Correct 27 ms 41088 KB Output is correct
4 Correct 26 ms 41088 KB Output is correct
5 Correct 26 ms 41088 KB Output is correct
6 Correct 26 ms 41088 KB Output is correct
7 Correct 27 ms 41088 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 64888 KB Output is correct
2 Correct 85 ms 64636 KB Output is correct
3 Correct 137 ms 72420 KB Output is correct
4 Correct 137 ms 75684 KB Output is correct
5 Correct 113 ms 68232 KB Output is correct
6 Correct 114 ms 68472 KB Output is correct
7 Correct 98 ms 68472 KB Output is correct
8 Correct 138 ms 79352 KB Output is correct
9 Correct 132 ms 77816 KB Output is correct
10 Correct 95 ms 65400 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 47956 KB Output is correct
2 Correct 50 ms 45560 KB Output is correct
3 Correct 60 ms 46704 KB Output is correct
4 Correct 53 ms 45816 KB Output is correct
5 Correct 53 ms 45432 KB Output is correct
6 Correct 63 ms 46584 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41088 KB Output is correct
2 Correct 27 ms 41088 KB Output is correct
3 Correct 27 ms 41088 KB Output is correct
4 Correct 26 ms 41088 KB Output is correct
5 Correct 26 ms 41088 KB Output is correct
6 Correct 26 ms 41088 KB Output is correct
7 Correct 27 ms 41088 KB Output is correct
8 Correct 76 ms 64888 KB Output is correct
9 Correct 85 ms 64636 KB Output is correct
10 Correct 137 ms 72420 KB Output is correct
11 Correct 137 ms 75684 KB Output is correct
12 Correct 113 ms 68232 KB Output is correct
13 Correct 114 ms 68472 KB Output is correct
14 Correct 98 ms 68472 KB Output is correct
15 Correct 138 ms 79352 KB Output is correct
16 Correct 132 ms 77816 KB Output is correct
17 Correct 95 ms 65400 KB Output is correct
18 Correct 62 ms 47956 KB Output is correct
19 Correct 50 ms 45560 KB Output is correct
20 Correct 60 ms 46704 KB Output is correct
21 Correct 53 ms 45816 KB Output is correct
22 Correct 53 ms 45432 KB Output is correct
23 Correct 63 ms 46584 KB Output is correct
24 Correct 101 ms 69052 KB Output is correct
25 Correct 123 ms 71416 KB Output is correct
26 Correct 93 ms 68120 KB Output is correct
27 Correct 151 ms 74872 KB Output is correct
28 Correct 182 ms 72696 KB Output is correct
29 Correct 156 ms 62428 KB Output is correct