oj.uz

Submission #89702

# Submission time Handle Problem Language Result Execution time Memory
89702 2018-12-18T07:03:12 Z mra2322001 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 539 ms 187756 KB 
/*
    Bai nay ta khong can co dinh 2 vi tri, ta chi can co dinh 1 vi tri la du, vi tri con lai dung dem
    --> rut ra: co bai ta can co dinh nhieu thuws thi thuwr coos dinhj 1 cais rooif cais kia dungf cachs naof
    ddeer nos bieens maats ddi laf dduowcj
*/
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int id(char x){
    if(x=='A') return 0;
    if(x=='G') return 1;
    if(x=='C') return 2;
    if(x=='U') return 3;
}

int t1[2000002][4], t2[2000002][4], cnt1 = 1, cnt2 = 1, cnt = 0, low[N*20], high[N*20];
int n, q;
string s[N];
vector <vector <int> > v;

void add2(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        char now = cur[i];
        if(t2[u][id(now)]==0){
            t2[u][id(now)] = ++cnt2;
        }
        u = t2[u][id(now)];
    }
}

void add1(string cur, int e){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        char now = cur[i];
        if(t1[u][id(now)]==0){
            t1[u][id(now)] = ++cnt1;
        }
        u = t1[u][id(now)];
        v[u].emplace_back(e);
    }
}

void dfs(int u, int p){
    low[u] = ++cnt;
    f0(i, 4){
        if(t2[u][i]==0) continue;
        dfs(t2[u][i], u);
    }
    high[u] = ++cnt;
}

int get_low(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        u = t2[u][id(cur[i])];
    }
    return low[u];
}

int find1(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        if(t1[u][id(cur[i])]==0) return 0;
        u = t1[u][id(cur[i])];
    }
    return u;
}

pair <int, int> find2(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        if(t2[u][id(cur[i])]==0) return {-1, -1};
        u = t2[u][id(cur[i])];
    }
    return {low[u], high[u]};
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> q;
    int dem = 0;
    f1(i, n){
        cin >> s[i];
        dem += s[i].size();
        reverse(s[i].begin(), s[i].end());
        add2(s[i]);
    }
    v.resize(dem + 1);
    dfs(1, 1);
    f1(i, n){
        int now = get_low(s[i]);
        reverse(s[i].begin(), s[i].end());
        add1(s[i], now);
    }
    f1(i, cnt1) sort(v[i].begin(), v[i].end());
    while(q--){
        string s1, s2;
        cin >> s1;
        cin >> s2;
        reverse(s2.begin(), s2.end());
        int g1 = find1(s1);
        pair <int, int> cur = find2(s2);
        if(g1==0 || cur.first==-1){
            cout << 0 << "\n";
            continue;
        }
        int k1 = lower_bound(v[g1].begin(), v[g1].end(), cur.first) - v[g1].begin();
        int k2 = upper_bound(v[g1].begin(), v[g1].end(), cur.second) - v[g1].begin() - 1;
        int res = k2 - k1 + 1;
        res = max(res, 0);
        cout << res << "\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int id(char)':
selling_rna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 115084 KB Output is correct
2 Correct 378 ms 116388 KB Output is correct
3 Correct 362 ms 155924 KB Output is correct
4 Correct 341 ms 155924 KB Output is correct
5 Correct 351 ms 155924 KB Output is correct
6 Correct 353 ms 155924 KB Output is correct
7 Correct 149 ms 155924 KB Output is correct
8 Correct 359 ms 155924 KB Output is correct
9 Correct 299 ms 155924 KB Output is correct
10 Correct 313 ms 155924 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 155924 KB Output is correct
2 Correct 81 ms 155924 KB Output is correct
3 Correct 100 ms 155924 KB Output is correct
4 Correct 77 ms 155924 KB Output is correct
5 Correct 80 ms 155924 KB Output is correct
6 Correct 99 ms 155924 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 4 ms 3832 KB Output is correct
3 Correct 5 ms 3832 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3832 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 318 ms 115084 KB Output is correct
9 Correct 378 ms 116388 KB Output is correct
10 Correct 362 ms 155924 KB Output is correct
11 Correct 341 ms 155924 KB Output is correct
12 Correct 351 ms 155924 KB Output is correct
13 Correct 353 ms 155924 KB Output is correct
14 Correct 149 ms 155924 KB Output is correct
15 Correct 359 ms 155924 KB Output is correct
16 Correct 299 ms 155924 KB Output is correct
17 Correct 313 ms 155924 KB Output is correct
18 Correct 110 ms 155924 KB Output is correct
19 Correct 81 ms 155924 KB Output is correct
20 Correct 100 ms 155924 KB Output is correct
21 Correct 77 ms 155924 KB Output is correct
22 Correct 80 ms 155924 KB Output is correct
23 Correct 99 ms 155924 KB Output is correct
24 Correct 416 ms 155924 KB Output is correct
25 Correct 465 ms 155924 KB Output is correct
26 Correct 379 ms 157692 KB Output is correct
27 Correct 368 ms 187756 KB Output is correct
28 Correct 539 ms 187756 KB Output is correct
29 Correct 276 ms 187756 KB Output is correct