oj.uz

Submission #196747

# Submission time Handle Problem Language Result Execution time Memory
196747 2020-01-17T04:55:55 Z darkkcyan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 607 ms 128504 KB 
// vim: foldmethod=marker
// Thu Jan 16 21:39:21 MSK 2020: START coding
#include <bits/stdc++.h>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }

/*{{{*/
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
int debug = 1;
#define DB(...) stringstream CONCAT(ss, __LINE__); CONCAT(ss, __LINE__) << __VA_ARGS__; debug_block CONCAT(dbbl, __LINE__)(CONCAT(ss, __LINE__).str())
#else
int debug = 0;
#define DB(...)
#endif
int __db_level = 0;
#define clog if (debug) cerr << string(__db_level * 2, ' ')
struct debug_block {
    string name;
    debug_block(const string& name_): name(name_) { clog << "{ " << name << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << name << endl; }
};
#define deb(...) "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]"
#define debln(...)  clog << "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]" << endl
#define _ << ", " <<
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return out << "(" << p.first _ p.second << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return out << "(" << get<0>(t) _ get<1>(t) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return out << "(" << get<0>(t) _ get<1>(t) _ get<2>(t) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) { 
    out << "{";
    if (len(container)) out << container[0];
    rep1(i, len(container) - 1) out _ container[i];
    return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }
/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////

#define char short
const int maxn = 101010;
unordered_map<char, char> char_map = {
    {'A', 0},
    {'C', 1},
    {'G', 2},
    {'U', 3}
};

vector<char> transform_rna(const string s) {
    vector<char> ans(len(s));
    rep(i, len(s)) ans[i] = char_map[s[i]];
    return ans;
}

template<class container>
struct trie {
    trie* child[4];
    int cnt_all;
    trie(): child{0}, cnt_all(0) {}
    ~trie() {
        rep(i, 4) if(child[i]) delete child[i];
    }

    void insert(const container& s) {
        trie* cur = this;
        ++cnt_all;
        for (auto i: s) {
            if (!cur->child[(int)i]) cur->child[(int)i] = new trie();
            cur = cur->child[(int)i];
            ++cur->cnt_all;
        }
    }

    int get_self_cnt() {
        int ans = cnt_all;
        rep(i, 4) if (child[i]) ans -= child[i]->cnt_all;
        if (ans < 0) {
            assert(false);
        }
        return ans;
    }

    // return (lower_bound, cnt)
    pair<int, int> find_bound(const container& s) { 
        int cnt_lower = 0;
        trie* cur = this;
        for (auto i: s) {
            cnt_lower += cur->get_self_cnt();
            rep(f, i) 
                if (cur->child[f])
                    cnt_lower += cur->child[f]->cnt_all;
            if (!cur->child[(int)i]) return {cnt_lower, 0};
            cur = cur->child[(int)i];
        }
        return {cnt_lower, cur->cnt_all};
    }
};

using trie_char = trie<vector<char>>;

int n, m;
vector<char> a[maxn];

struct query {
    int id;
    int pos;
    int sign;
    vector<char> what;
    query(int i, int p, int s, const vector<char>& w): id(i), pos(p), sign(s), what(w) {}
};

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep(i, n) {
        string s; cin >> s;
        a[i] = transform_rna(s);
    }

    trie_char root;
    rep(i, n) {
        root.insert(a[i]);
        a[i].clear();
    }

    // in other words, this part is "sorting".
    queue<pair<trie_char*, int>> qu;  
    for (qu.emplace(&root, 0); len(qu); qu.pop()) {
        auto [cur_root, cnt_lower] = qu.front();
        cnt_lower += cur_root->get_self_cnt();
        rep(i, 4) {
            if (!cur_root->child[i]) continue;
            qu.emplace(cur_root->child[i], cnt_lower);
            rep(f, cur_root->child[i]->cnt_all) {
                a[f + cnt_lower].push_back((char)i);
            }
            cnt_lower += cur_root->child[i]->cnt_all;
        }
    }

    vector<query> all_query;

    rep(q, m) {
        string pref, suff; cin >> pref >> suff;
        auto tr_pref = transform_rna(pref), tr_suff = transform_rna(suff);
        reverse(tr_suff.begin(), tr_suff.end());

        auto bound = root.find_bound(tr_pref);
        all_query.emplace_back(q, bound.first, -1, tr_suff);
        all_query.emplace_back(q, bound.first + bound.second, 1, tr_suff);
    }

    sort(all_query.begin(), all_query.end(), [](const auto& q1, const auto&q2) { return q1.pos < q2.pos; });
    for (auto q: all_query) {
        DB(q.id);
        debln(q.pos); 
        debln(q.what);
        debln(q.sign);
    }

    trie_char quering_root;
    int qr = 0;
    while (qr < len(all_query) and all_query[qr].pos == 0) ++qr;
    vector<int> ans(m);

    rep1(i, n) {
        DB(deb(i));
        reverse(a[i - 1].begin(), a[i - 1].end());
        debln(a[i - 1]);
        quering_root.insert(a[i - 1]);

        for (; qr < len(all_query) and all_query[qr].pos == i; ++qr) {
            DB("query " << deb(qr));
            debln(all_query[qr].what);
            debln(quering_root.find_bound(all_query[qr].what));
            ans[all_query[qr].id] += all_query[qr].sign * quering_root.find_bound(all_query[qr].what).second;
        }
    }

    rep(i, m) cout << ans[i] << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2812 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2780 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2736 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 107156 KB Output is correct
2 Correct 399 ms 102860 KB Output is correct
3 Correct 587 ms 113972 KB Output is correct
4 Correct 568 ms 109552 KB Output is correct
5 Correct 530 ms 126684 KB Output is correct
6 Correct 548 ms 128504 KB Output is correct
7 Correct 231 ms 19676 KB Output is correct
8 Correct 501 ms 88312 KB Output is correct
9 Correct 467 ms 78480 KB Output is correct
10 Correct 357 ms 68208 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12332 KB Output is correct
2 Correct 51 ms 8872 KB Output is correct
3 Correct 64 ms 11652 KB Output is correct
4 Correct 55 ms 11332 KB Output is correct
5 Correct 64 ms 8792 KB Output is correct
6 Correct 67 ms 11648 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2812 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2780 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2736 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 404 ms 107156 KB Output is correct
9 Correct 399 ms 102860 KB Output is correct
10 Correct 587 ms 113972 KB Output is correct
11 Correct 568 ms 109552 KB Output is correct
12 Correct 530 ms 126684 KB Output is correct
13 Correct 548 ms 128504 KB Output is correct
14 Correct 231 ms 19676 KB Output is correct
15 Correct 501 ms 88312 KB Output is correct
16 Correct 467 ms 78480 KB Output is correct
17 Correct 357 ms 68208 KB Output is correct
18 Correct 70 ms 12332 KB Output is correct
19 Correct 51 ms 8872 KB Output is correct
20 Correct 64 ms 11652 KB Output is correct
21 Correct 55 ms 11332 KB Output is correct
22 Correct 64 ms 8792 KB Output is correct
23 Correct 67 ms 11648 KB Output is correct
24 Correct 445 ms 93268 KB Output is correct
25 Correct 469 ms 97644 KB Output is correct
26 Correct 381 ms 90664 KB Output is correct
27 Correct 607 ms 99172 KB Output is correct
28 Correct 390 ms 41328 KB Output is correct
29 Correct 266 ms 24192 KB Output is correct