Submission #213440

#	Time	Username	Problem	Language	Result	Execution time	Memory
213440		DS007	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	74 ms	6784 KiB

selling_rna

#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<string, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>

struct query {
    string p, q;
    int i, ans;

    query() {
        p = "";
        q = "";
        i = ans = -1;
    }
};

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

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

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

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

    query q[m];
    for (int i = 0; i < m; i++) {
        cin >> q[i].p >> q[i].q;
        q[i].i = i;
    }

    sort(q, q + m, [](auto &q1, auto &q2) {
        return q1.p < q2.p;
    });

    index_set is;
    int lp = 0, rp = 0;

    for (int i = 0; i < m; i++) {
        while (lp != n && (s[lp] < q[i].p || compatible(s[lp], q[i].p)))
            is.insert(reverse(s[lp++]));
        while (rp != n && s[rp] < q[i].p)
            is.erase(is.find(reverse(s[rp++])));

        string temp = reverse(q[i].q);
        temp[temp.length() - 1]++;
        q[i].ans = is.order_of_key(temp) - is.order_of_key(reverse(q[i].q));
    }

    sort(q, q + m, [](auto &q1, auto &q2) {
        return q1.i < q2.i;
    });

    for (int i = 0; i < m; i++)
        cout << q[i].ans << "\n";
}

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

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40