oj.uz

Submission #1088181

# Submission time Handle Problem Language Result Execution time Memory
1088181 2024-09-14T05:06:15 Z TrinhKhanhDung Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 241 ms 319308 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int lim = 2e6 + 10, MAX = 1e5 + 10;

int n[lim][26];
vector<int> idx[lim];
int timer;

int N, Q;
string a[MAX];

void solve(){
    memset(n, -1, sizeof n);
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) cin >> a[i];
    sort(a + 1, a + N + 1);
    for(int i = 1; i <= N; i++){
        int p = 0;
        for(int j = sz(a[i]) - 1; j >= 0; j--){
            int id = a[i][j] - 'A';
            if(n[p][id] == -1) n[p][id] = ++timer;
            p = n[p][id];
            idx[p].push_back(i);
        }
    }
    while(Q--){
        string x, y; cin >> x >> y;
        int l = lower_bound(a + 1, a + N + 1, x) - a;
        x.back()++;
        int r = lower_bound(a + 1, a + N + 1, x) - a - 1;
        if(l > r){
            cout << 0 << '\n';
            continue;
        }
        int p = 0;
        for(int j = sz(y) - 1; j >= 0; j--){
            int id = y[j] - 'A';
            p = n[p][id];
            if(p == -1) break;
        }
        if(p == -1) cout << 0 << '\n';
        else{
            int pl = lower_bound(ALL(idx[p]), l) - idx[p].begin();
            int pr = upper_bound(ALL(idx[p]), r) - idx[p].begin();
            cout << pr - pl << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("FBUY.inp","r",stdin);
    // freopen("FBUY.out","w",stdout);

    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 253840 KB Output is correct
2 Correct 124 ms 253896 KB Output is correct
3 Correct 133 ms 253972 KB Output is correct
4 Correct 115 ms 254000 KB Output is correct
5 Correct 115 ms 254036 KB Output is correct
6 Correct 116 ms 254032 KB Output is correct
7 Correct 120 ms 254032 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 319308 KB Output is correct
2 Correct 209 ms 318288 KB Output is correct
3 Correct 153 ms 270936 KB Output is correct
4 Correct 143 ms 270928 KB Output is correct
5 Correct 186 ms 296020 KB Output is correct
6 Correct 201 ms 296528 KB Output is correct
7 Correct 146 ms 269324 KB Output is correct
8 Correct 210 ms 290128 KB Output is correct
9 Correct 197 ms 286224 KB Output is correct
10 Correct 175 ms 283216 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 254804 KB Output is correct
2 Correct 132 ms 254804 KB Output is correct
3 Correct 134 ms 254736 KB Output is correct
4 Correct 128 ms 254660 KB Output is correct
5 Correct 131 ms 254776 KB Output is correct
6 Correct 138 ms 254548 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 253840 KB Output is correct
2 Correct 124 ms 253896 KB Output is correct
3 Correct 133 ms 253972 KB Output is correct
4 Correct 115 ms 254000 KB Output is correct
5 Correct 115 ms 254036 KB Output is correct
6 Correct 116 ms 254032 KB Output is correct
7 Correct 120 ms 254032 KB Output is correct
8 Correct 206 ms 319308 KB Output is correct
9 Correct 209 ms 318288 KB Output is correct
10 Correct 153 ms 270936 KB Output is correct
11 Correct 143 ms 270928 KB Output is correct
12 Correct 186 ms 296020 KB Output is correct
13 Correct 201 ms 296528 KB Output is correct
14 Correct 146 ms 269324 KB Output is correct
15 Correct 210 ms 290128 KB Output is correct
16 Correct 197 ms 286224 KB Output is correct
17 Correct 175 ms 283216 KB Output is correct
18 Correct 133 ms 254804 KB Output is correct
19 Correct 132 ms 254804 KB Output is correct
20 Correct 134 ms 254736 KB Output is correct
21 Correct 128 ms 254660 KB Output is correct
22 Correct 131 ms 254776 KB Output is correct
23 Correct 138 ms 254548 KB Output is correct
24 Correct 217 ms 310608 KB Output is correct
25 Correct 241 ms 310864 KB Output is correct
26 Correct 216 ms 310192 KB Output is correct
27 Correct 151 ms 270416 KB Output is correct
28 Correct 239 ms 276188 KB Output is correct
29 Correct 186 ms 262608 KB Output is correct