oj.uz

Submission #1099412

# Submission time Handle Problem Language Result Execution time Memory
1099412 2024-10-11T09:21:47 Z underwaterkillerwhale Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 478 ms 659180 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

int n, Q;
vector<string> vec;

string Rev (string &S) {
    static string res;
    res = "";
    reb (i, SZ(S) - 1, 0) res += S[i];
    return res;
}

struct tNode {
    tNode *child[26];
    vector<int> vec;

    tNode () {
        rep (i, 0, 25) child[i] = NULL;
    }
}*proot = new tNode(), *sroot = new tNode();

void Add (tNode *cur, string S, int idx) {
    iter (&id, S) {
        int c = id - 'A';
        if (cur->child[c] == NULL) cur->child[c] = new tNode();
        cur = cur->child[c];
        cur->vec.pb(idx);
    }
}

pii getRange (tNode *cur, string &S) {
    iter (&id, S) {
        int c = id - 'A';
        if (cur->child[c] == NULL) {
            return MP(INF, 0);
        }
        cur = cur->child[c];
    }
    return MP(cur->vec[0], cur->vec.back());
}

int get (tNode *cur, string S, pii Range) {
    if (Range.fs > Range.se) return 0;
    iter (&id, S) {
        int c = id - 'A';
        if (cur->child[c] == NULL)
            return 0;
        cur = cur->child[c];
    }
    int L = lower_bound(ALL(cur->vec), Range.fs) - cur->vec.begin();
    int R = upper_bound(ALL(cur->vec), Range.se) - cur->vec.begin();
    return R - L;
}

void solution () {
    cin >> n >> Q;
    vec.resize(n + 1, "");
    rep (i, 1, n) {
        cin >> vec[i];
    }
    sort (vec.begin() + 1, vec.end());
    rep (i, 1, n) {
        Add(proot, vec[i], i);
        Add(sroot, Rev(vec[i]), i);
    }
    rep (i, 1, Q) {
        string T, Y;
        cin >> T >> Y;
        cout << get(sroot, Rev(Y), getRange(proot, T)) <<"\n";
    }

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +10

5 5
01101
10001
00110
10101
00100
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 538432 KB Output is correct
2 Correct 310 ms 509356 KB Output is correct
3 Correct 291 ms 530516 KB Output is correct
4 Correct 313 ms 504804 KB Output is correct
5 Correct 478 ms 649300 KB Output is correct
6 Correct 468 ms 659180 KB Output is correct
7 Correct 63 ms 19796 KB Output is correct
8 Correct 303 ms 394500 KB Output is correct
9 Correct 231 ms 331860 KB Output is correct
10 Correct 192 ms 322900 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3400 KB Output is correct
2 Correct 15 ms 3676 KB Output is correct
3 Correct 18 ms 3524 KB Output is correct
4 Correct 17 ms 2904 KB Output is correct
5 Correct 15 ms 3716 KB Output is correct
6 Correct 21 ms 3420 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 338 ms 538432 KB Output is correct
9 Correct 310 ms 509356 KB Output is correct
10 Correct 291 ms 530516 KB Output is correct
11 Correct 313 ms 504804 KB Output is correct
12 Correct 478 ms 649300 KB Output is correct
13 Correct 468 ms 659180 KB Output is correct
14 Correct 63 ms 19796 KB Output is correct
15 Correct 303 ms 394500 KB Output is correct
16 Correct 231 ms 331860 KB Output is correct
17 Correct 192 ms 322900 KB Output is correct
18 Correct 20 ms 3400 KB Output is correct
19 Correct 15 ms 3676 KB Output is correct
20 Correct 18 ms 3524 KB Output is correct
21 Correct 17 ms 2904 KB Output is correct
22 Correct 15 ms 3716 KB Output is correct
23 Correct 21 ms 3420 KB Output is correct
24 Correct 307 ms 440656 KB Output is correct
25 Correct 314 ms 440660 KB Output is correct
26 Correct 314 ms 435540 KB Output is correct
27 Correct 250 ms 435028 KB Output is correct
28 Correct 136 ms 78812 KB Output is correct
29 Correct 66 ms 13500 KB Output is correct