oj.uz

Submission #233062

# Submission time Handle Problem Language Result Execution time Memory
233062 2020-05-19T05:44:05 Z triple_fault Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 206356 KB 
/* May 18 2020 */

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <random>
#include <iostream>
#include <string>

#define ll long long

using namespace std;

ll n, m;

struct trie {
    map<char, trie*> children;
    vector<ll> indexes;

    void insert(string s, ll l, ll r, ll idx) {
        indexes.push_back(idx);
        if (l > r) return;

        char c = s[l];
        if (children.find(c) == children.end()) 
            children[c] = new trie();
        children[c]->insert(s, l + 1, r, idx);
    }

    ll cnt(string s, ll l, ll r, ll tl, ll tr) {
        if (l > r) 
            return lower_bound(indexes.begin(), indexes.end(), tr) - 
                lower_bound(indexes.begin(), indexes.end(), tl);
        char c = s[l];
        if (children.find(c) == children.end()) return 0;
        return children[c]->cnt(s, l + 1, r, tl, tr);
    }
} main_trie;

string rev(string s) {
    reverse(s.begin(), s.end());
    return s;
}

int main(void) {
    scanf("%lld %lld", &n, &m);
    vector<string> vals(n);
    for (ll i = 0; i < n; ++i) cin >> vals[i];
    sort(vals.begin(), vals.end());

    for (ll i = 0; i < n; ++i)
        main_trie.insert(rev(vals[i]), 0, vals[i].length() - 1, i);

    while (m --) {
        string x, y; cin >> x >> y;
        ll l = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
        ++x.back();
        ll r = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
        printf("%lld\n", main_trie.cnt(rev(y), 0, y.length() - 1, l, r));
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1599 ms 206356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 4076 KB Output is correct
2 Correct 122 ms 3704 KB Output is correct
3 Correct 151 ms 3956 KB Output is correct
4 Correct 124 ms 3320 KB Output is correct
5 Correct 134 ms 3196 KB Output is correct
6 Correct 159 ms 3696 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Execution timed out 1599 ms 206356 KB Time limit exceeded
9 Halted 0 ms 0 KB -