oj.uz

Submission #196830

# Submission time Handle Problem Language Result Execution time Memory
196830 2020-01-17T05:08:05 Z darkkcyan Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 415 ms 124304 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 ////////////////////////////////////////////////////////////

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;

    trie_char root;
    rep(i, n) {
        string s; cin >> s;
        a[i] = transform_rna(s);
        root.insert(a[i]);
    }

    sort(a, a + n);

    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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 101680 KB Output is correct
2 Correct 348 ms 97128 KB Output is correct
3 Correct 359 ms 104588 KB Output is correct
4 Correct 345 ms 100108 KB Output is correct
5 Correct 382 ms 122576 KB Output is correct
6 Correct 377 ms 124304 KB Output is correct
7 Correct 226 ms 14380 KB Output is correct
8 Correct 404 ms 82732 KB Output is correct
9 Correct 390 ms 71548 KB Output is correct
10 Correct 274 ms 65004 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12284 KB Output is correct
2 Correct 69 ms 8660 KB Output is correct
3 Correct 70 ms 11524 KB Output is correct
4 Correct 59 ms 11396 KB Output is correct
5 Correct 55 ms 8724 KB Output is correct
6 Correct 75 ms 11652 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 372 ms 101680 KB Output is correct
9 Correct 348 ms 97128 KB Output is correct
10 Correct 359 ms 104588 KB Output is correct
11 Correct 345 ms 100108 KB Output is correct
12 Correct 382 ms 122576 KB Output is correct
13 Correct 377 ms 124304 KB Output is correct
14 Correct 226 ms 14380 KB Output is correct
15 Correct 404 ms 82732 KB Output is correct
16 Correct 390 ms 71548 KB Output is correct
17 Correct 274 ms 65004 KB Output is correct
18 Correct 76 ms 12284 KB Output is correct
19 Correct 69 ms 8660 KB Output is correct
20 Correct 70 ms 11524 KB Output is correct
21 Correct 59 ms 11396 KB Output is correct
22 Correct 55 ms 8724 KB Output is correct
23 Correct 75 ms 11652 KB Output is correct
24 Correct 340 ms 87372 KB Output is correct
25 Correct 389 ms 92024 KB Output is correct
26 Correct 325 ms 85000 KB Output is correct
27 Correct 340 ms 89644 KB Output is correct
28 Correct 415 ms 36076 KB Output is correct
29 Correct 300 ms 24092 KB Output is correct