oj.uz

Submission #213460

# Submission time Handle Problem Language Result Execution time Memory
213460 2020-03-25T21:35:14 Z DS007 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 964 ms 129892 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define index_set tree<pair<string, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define mid (l + r) / 2
#define child v * 2

const int N = 1e5;
vector<string> t[N * 4];
string s[N];

bool compatible(const string &a, const string &b) {
    return a.substr(0, b.length()) == b;
}

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

void build(int v, int l, int r) {
    if (l == r) {
        t[v].push_back(reverse(s[l]));
        return;
    }

    build(child, l, mid);
    build(child + 1, mid + 1, r);

    int lp = 0, rp = 0;
    while (lp != t[child].size() && rp != t[child + 1].size()) {
        if (t[child][lp] < t[child + 1][rp])
            t[v].push_back(t[child][lp++]);
        else
            t[v].push_back(t[child + 1][rp++]);
    }
    while (lp != t[child].size())
        t[v].push_back(t[child][lp++]);
    while (rp != t[child + 1].size())
        t[v].push_back(t[child + 1][rp++]);
}

int query(int v, int l, int r, int tl, int tr, pair<string, int> &up, pair<string, int> &down) {
    if (tl > tr)
        return 0;
    else if (l == tl && r == tr)
        return (lower_bound(t[v].begin(), t[v].end(), up.first) - t[v].begin()) - (lower_bound(t[v].begin(), t[v].end(), down.first) - t[v].begin());
    return query(child, l, mid, tl, min(mid, tr), up, down) + query(child + 1, mid + 1, r, max(mid + 1, tl), tr, up, down);
}

void solveTestCase() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n);
    build(1, 0, n - 1);

    /*for (int i = 0; i < n; i++)
        cout << s[i] << " ";
    cout << endl;*/

    for (int i = 0; i < m; i++) {
        string p, q;
        cin >> p >> q;

        string temp = p;
        temp[p.length() - 1]++;
        int tl = lower_bound(s, s + n, p) - s, tr = lower_bound(s, s + n, temp) - s - 1;
        temp = reverse(q);
        temp[q.length() - 1]++;
        pair<string, int> up = {temp, -1}, down = {reverse(q), -1};
        cout << query(1, 0, n - 1, tl, tr, up, down) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message

selling_rna.cpp: In function 'void build(long long int, long long int, long long int)':
selling_rna.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size() && rp != t[child + 1].size()) {
            ~~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:34:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size() && rp != t[child + 1].size()) {
                                     ~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size())
            ~~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rp != t[child + 1].size())
            ~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12928 KB Output is correct
2 Correct 12 ms 12800 KB Output is correct
3 Correct 13 ms 12928 KB Output is correct
4 Correct 12 ms 12928 KB Output is correct
5 Correct 12 ms 12800 KB Output is correct
6 Correct 12 ms 12928 KB Output is correct
7 Correct 14 ms 12800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 43512 KB Output is correct
2 Correct 86 ms 49012 KB Output is correct
3 Correct 72 ms 46072 KB Output is correct
4 Correct 83 ms 49012 KB Output is correct
5 Correct 59 ms 36980 KB Output is correct
6 Correct 59 ms 37236 KB Output is correct
7 Correct 61 ms 38264 KB Output is correct
8 Correct 72 ms 51060 KB Output is correct
9 Correct 70 ms 51060 KB Output is correct
10 Correct 68 ms 48628 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 46952 KB Output is correct
2 Correct 142 ms 30956 KB Output is correct
3 Correct 183 ms 42860 KB Output is correct
4 Correct 116 ms 37228 KB Output is correct
5 Correct 113 ms 30772 KB Output is correct
6 Correct 160 ms 43120 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12928 KB Output is correct
2 Correct 12 ms 12800 KB Output is correct
3 Correct 13 ms 12928 KB Output is correct
4 Correct 12 ms 12928 KB Output is correct
5 Correct 12 ms 12800 KB Output is correct
6 Correct 12 ms 12928 KB Output is correct
7 Correct 14 ms 12800 KB Output is correct
8 Correct 51 ms 43512 KB Output is correct
9 Correct 86 ms 49012 KB Output is correct
10 Correct 72 ms 46072 KB Output is correct
11 Correct 83 ms 49012 KB Output is correct
12 Correct 59 ms 36980 KB Output is correct
13 Correct 59 ms 37236 KB Output is correct
14 Correct 61 ms 38264 KB Output is correct
15 Correct 72 ms 51060 KB Output is correct
16 Correct 70 ms 51060 KB Output is correct
17 Correct 68 ms 48628 KB Output is correct
18 Correct 158 ms 46952 KB Output is correct
19 Correct 142 ms 30956 KB Output is correct
20 Correct 183 ms 42860 KB Output is correct
21 Correct 116 ms 37228 KB Output is correct
22 Correct 113 ms 30772 KB Output is correct
23 Correct 160 ms 43120 KB Output is correct
24 Correct 175 ms 55280 KB Output is correct
25 Correct 301 ms 55664 KB Output is correct
26 Correct 138 ms 55308 KB Output is correct
27 Correct 183 ms 55280 KB Output is correct
28 Correct 964 ms 129892 KB Output is correct
29 Correct 420 ms 86504 KB Output is correct