oj.uz

Submission #897071

# Submission time Handle Problem Language Result Execution time Memory
897071 2024-01-02T13:58:39 Z trytovoi Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 725 ms 740776 KB 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
#include "debug2.h"
#else
#define debug(...) 42
#endif
 
template<typename T> bool ckmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; } 
template<typename T> bool ckmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; } 
 
#define REP(i, n) for(int i = 0, ____n = (n); i < ____n; ++i)
#define REPD(i, n) for(int i = (n) - 1; i >= 0; --i)
#define __builtin_popcount __builtin_popcountll
#define left  _______left
#define right _______right
#define MASK(x) (1LL << (x))
#define BIT(mask, x) (((mask) >> (x)) & 1)
#define SZ(x) (int) ((x).size())
#define ALL(x) (x).begin(), (x).end()
#define SQR(x) (1LL * (x) * (x))
#define BETWEEN(l, x, r) ((l) <= (x) && (x) <= (r))
 
const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int INF = (int) 1e9 + 7;
const long long LINF = (long long) 1e18 + 7;
const int MX = (int) 1e5 + 5;
const int BLOCK = 320;
 
struct node {
    node *nxt[30];
    vector<int> ids;
    node(void) {
        ids.clear();
        REP(i, 26) nxt[i] = NULL;
    }
};
 
node *root[2];
 
void addString(bool prefix, const string& s, int id) {
    node *cur = root[prefix];
    for (char ch : s) {
        int p = ch - 'A';
        if (cur->nxt[p] == NULL) cur->nxt[p] = new node();
        cur = cur->nxt[p];
        cur->ids.push_back(id);
    }
}
 
vector<int> getString(bool prefix, const string& s) {
    node *cur = root[prefix];
    for (char ch : s) {
        int p = ch - 'A';
        if (cur->nxt[p] == NULL) return vector<int>();
        cur = cur->nxt[p];
    }
    return cur->ids;
}
 
int n, q;
string S[MX];
 
signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    REP(i, 2) root[i] = new node();
    REP(i, n) cin >> S[i];
    sort(S, S + n);
    REP(i, n) {
        addString(true, S[i], i);
        reverse(ALL(S[i]));
        addString(false, S[i], i);
    }
 
    while (q--) {
        string pref, suf; cin >> pref >> suf;
        reverse(ALL(suf));
        vector<int> vec_prefix = getString(true, pref);
        vector<int> vec_suffix = getString(false, suf);
 
        if (vec_prefix.empty() || vec_suffix.empty()) {
            cout << "0\n";
            continue;
        }
 
        int left = (int) (lower_bound(ALL(vec_suffix), vec_prefix[0]) - vec_suffix.begin());
        int right = (int) (upper_bound(ALL(vec_suffix), vec_prefix.back()) - vec_suffix.begin());
 
        cout << right - left << '\n';
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 605408 KB Output is correct
2 Correct 337 ms 572984 KB Output is correct
3 Correct 324 ms 596516 KB Output is correct
4 Correct 340 ms 568404 KB Output is correct
5 Correct 474 ms 729788 KB Output is correct
6 Correct 472 ms 740776 KB Output is correct
7 Correct 86 ms 26124 KB Output is correct
8 Correct 334 ms 445592 KB Output is correct
9 Correct 269 ms 375604 KB Output is correct
10 Correct 214 ms 364372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 5492 KB Output is correct
2 Correct 54 ms 6516 KB Output is correct
3 Correct 77 ms 5884 KB Output is correct
4 Correct 51 ms 5180 KB Output is correct
5 Correct 56 ms 6536 KB Output is correct
6 Correct 82 ms 5948 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 1 ms 3416 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 405 ms 605408 KB Output is correct
9 Correct 337 ms 572984 KB Output is correct
10 Correct 324 ms 596516 KB Output is correct
11 Correct 340 ms 568404 KB Output is correct
12 Correct 474 ms 729788 KB Output is correct
13 Correct 472 ms 740776 KB Output is correct
14 Correct 86 ms 26124 KB Output is correct
15 Correct 334 ms 445592 KB Output is correct
16 Correct 269 ms 375604 KB Output is correct
17 Correct 214 ms 364372 KB Output is correct
18 Correct 219 ms 5492 KB Output is correct
19 Correct 54 ms 6516 KB Output is correct
20 Correct 77 ms 5884 KB Output is correct
21 Correct 51 ms 5180 KB Output is correct
22 Correct 56 ms 6536 KB Output is correct
23 Correct 82 ms 5948 KB Output is correct
24 Correct 310 ms 496112 KB Output is correct
25 Correct 385 ms 496540 KB Output is correct
26 Correct 314 ms 490268 KB Output is correct
27 Correct 304 ms 489760 KB Output is correct
28 Correct 725 ms 88400 KB Output is correct
29 Correct 108 ms 15284 KB Output is correct