oj.uz

Submission #1087853

# Submission time Handle Problem Language Result Execution time Memory
1087853 2024-09-13T10:19:36 Z LOLOLO Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 289 ms 369232 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 3e6 + 100;
map <int, int> id[N];
vector <int> pos[N];

int cnt = 1;

void add(string s, int i) {
    int cur = 0;
    for (auto x : s) {
        if (id[cur][x] == 0)
            id[cur][x] = cnt++;

        cur = id[cur][x];
        pos[cur].pb(i);
    }
}

int get(string s, int l, int r) {
    int cur = 0;
    for (auto x : s) {
        if (id[cur][x] == 0)
            return 0;

        cur = id[cur][x];
    }

    int L = lower_bound(all(pos[cur]), l) - pos[cur].begin();
    int R = upper_bound(all(pos[cur]), r) - pos[cur].begin();
    return R - L;
}

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

    vector <string> ss;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ss.pb(s);
    }

    sort(all(ss));

    for (int i = 0; i < sz(ss); i++) {
        string s = ss[i];
        reverse(all(s));
        add(s, i);
    }

    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        int l = lower_bound(all(ss), a) - ss.begin();
        a.back()++;
        int r = lower_bound(all(ss), a) - ss.begin() - 1;

        if (l > r) {
            cout << 0 << '\n';
            continue;
        }

        reverse(all(b));
        cout << get(b, l, r) << '\n';
    } 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 211796 KB Output is correct
2 Correct 97 ms 211792 KB Output is correct
3 Correct 83 ms 211748 KB Output is correct
4 Correct 90 ms 211704 KB Output is correct
5 Correct 88 ms 211748 KB Output is correct
6 Correct 95 ms 211752 KB Output is correct
7 Correct 84 ms 211712 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 369232 KB Output is correct
2 Correct 264 ms 363496 KB Output is correct
3 Correct 141 ms 229264 KB Output is correct
4 Correct 177 ms 229404 KB Output is correct
5 Correct 221 ms 311064 KB Output is correct
6 Correct 222 ms 312524 KB Output is correct
7 Correct 136 ms 227152 KB Output is correct
8 Correct 241 ms 281332 KB Output is correct
9 Correct 215 ms 272292 KB Output is correct
10 Correct 185 ms 268164 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 214276 KB Output is correct
2 Correct 103 ms 213648 KB Output is correct
3 Correct 107 ms 213844 KB Output is correct
4 Correct 104 ms 213964 KB Output is correct
5 Correct 110 ms 213288 KB Output is correct
6 Correct 107 ms 213812 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 211796 KB Output is correct
2 Correct 97 ms 211792 KB Output is correct
3 Correct 83 ms 211748 KB Output is correct
4 Correct 90 ms 211704 KB Output is correct
5 Correct 88 ms 211748 KB Output is correct
6 Correct 95 ms 211752 KB Output is correct
7 Correct 84 ms 211712 KB Output is correct
8 Correct 289 ms 369232 KB Output is correct
9 Correct 264 ms 363496 KB Output is correct
10 Correct 141 ms 229264 KB Output is correct
11 Correct 177 ms 229404 KB Output is correct
12 Correct 221 ms 311064 KB Output is correct
13 Correct 222 ms 312524 KB Output is correct
14 Correct 136 ms 227152 KB Output is correct
15 Correct 241 ms 281332 KB Output is correct
16 Correct 215 ms 272292 KB Output is correct
17 Correct 185 ms 268164 KB Output is correct
18 Correct 106 ms 214276 KB Output is correct
19 Correct 103 ms 213648 KB Output is correct
20 Correct 107 ms 213844 KB Output is correct
21 Correct 104 ms 213964 KB Output is correct
22 Correct 110 ms 213288 KB Output is correct
23 Correct 107 ms 213812 KB Output is correct
24 Correct 256 ms 343752 KB Output is correct
25 Correct 281 ms 344008 KB Output is correct
26 Correct 261 ms 342212 KB Output is correct
27 Correct 153 ms 228748 KB Output is correct
28 Correct 214 ms 246452 KB Output is correct
29 Correct 152 ms 223420 KB Output is correct