oj.uz

Submission #213459

# Submission time Handle Problem Language Result Execution time Memory
213459 2020-03-25T21:23:53 Z DS007 Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 264444 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;
index_set 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].insert({reverse(s[l]), l});
        return;
    }

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

    for (auto &i : t[child])
        t[v].insert(i);
    for (auto &i : t[child + 1])
        t[v].insert(i);
}

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 t[v].order_of_key(up) - t[v].order_of_key(down);
    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();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 53496 KB Output is correct
2 Correct 41 ms 53504 KB Output is correct
3 Correct 44 ms 53624 KB Output is correct
4 Correct 44 ms 53496 KB Output is correct
5 Correct 42 ms 53624 KB Output is correct
6 Correct 44 ms 53624 KB Output is correct
7 Correct 44 ms 53496 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 81784 KB Output is correct
2 Correct 145 ms 89080 KB Output is correct
3 Correct 129 ms 84984 KB Output is correct
4 Correct 152 ms 89080 KB Output is correct
5 Correct 106 ms 78456 KB Output is correct
6 Correct 105 ms 78712 KB Output is correct
7 Correct 120 ms 74744 KB Output is correct
8 Correct 137 ms 89208 KB Output is correct
9 Correct 132 ms 89208 KB Output is correct
10 Correct 147 ms 89212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 132344 KB Output is correct
2 Correct 367 ms 98552 KB Output is correct
3 Correct 484 ms 115192 KB Output is correct
4 Correct 361 ms 103928 KB Output is correct
5 Correct 325 ms 98552 KB Output is correct
6 Correct 428 ms 115192 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 53496 KB Output is correct
2 Correct 41 ms 53504 KB Output is correct
3 Correct 44 ms 53624 KB Output is correct
4 Correct 44 ms 53496 KB Output is correct
5 Correct 42 ms 53624 KB Output is correct
6 Correct 44 ms 53624 KB Output is correct
7 Correct 44 ms 53496 KB Output is correct
8 Correct 89 ms 81784 KB Output is correct
9 Correct 145 ms 89080 KB Output is correct
10 Correct 129 ms 84984 KB Output is correct
11 Correct 152 ms 89080 KB Output is correct
12 Correct 106 ms 78456 KB Output is correct
13 Correct 105 ms 78712 KB Output is correct
14 Correct 120 ms 74744 KB Output is correct
15 Correct 137 ms 89208 KB Output is correct
16 Correct 132 ms 89208 KB Output is correct
17 Correct 147 ms 89212 KB Output is correct
18 Correct 529 ms 132344 KB Output is correct
19 Correct 367 ms 98552 KB Output is correct
20 Correct 484 ms 115192 KB Output is correct
21 Correct 361 ms 103928 KB Output is correct
22 Correct 325 ms 98552 KB Output is correct
23 Correct 428 ms 115192 KB Output is correct
24 Correct 303 ms 99192 KB Output is correct
25 Correct 476 ms 99320 KB Output is correct
26 Correct 225 ms 99192 KB Output is correct
27 Correct 283 ms 99192 KB Output is correct
28 Execution timed out 1612 ms 264444 KB Time limit exceeded
29 Halted 0 ms 0 KB -