oj.uz

Submission #856981

# Submission time Handle Problem Language Result Execution time Memory
856981 2023-10-05T03:12:41 Z TS_2392 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 94 ms 112324 KB 
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 100005
using namespace std;
int n,m;
string S[N];
struct iii {
    string p,q;
    int id;
} T[N];
int cnt=0;
int Trie[2000005][4],Min[2000005],Max[2000005],End[2000005];
void Add(string s,int id) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) Trie[u][x]=++cnt;
        u=Trie[u][x];
        if (!Min[u]) Min[u]=id;
        Max[u]=id;
    }
}
ii Get(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) return {0,0};
        u=Trie[u][x];
    }
    return {Min[u],Max[u]};
}
vector < int > adj[N];
int ans[N];
void Add2(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) Trie[u][x]=++cnt;
        u=Trie[u][x];
        ++End[u];
    }
}
int Get2(string s) {
    int u=0;
    for (auto c : s) {
        int x=0;
        if (c=='U') x=1;
        else
        if (c=='A') x=2;
        else
        if (c=='C') x=3;
        if (!Trie[u][x]) return 0;
        u=Trie[u][x];
    }
    return End[u];
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //
    cin>>n>>m;
    FOR(i,1,n) cin>>S[i];
    sort(S+1,S+n+1);
    FOR(i,1,n) Add(S[i],i);
    //FOR(i,1,n) cout<<S[i]<<'\n';
    FOR(i,1,m) {
        cin>>T[i].p>>T[i].q;
        reverse(T[i].q.begin(),T[i].q.end());
        ii tmp=Get(T[i].p);
        int l=tmp.f,r=tmp.s;
        if (l && r && l<=r) {
            adj[l-1].pb(-i);
            adj[r].pb(i);
        }
        //cout<<l<<" "<<r<<'\n';
    }
    memset(Trie,0,sizeof(Trie));
    cnt=0;
    FOR(i,1,n) {
        reverse(S[i].begin(),S[i].end());
        Add2(S[i]);
        //cout<<S[i]<<'\n';
        for (auto j : adj[i]) {
            int id=abs(j);
            int val=Get2(T[id].q);
            if (j<0) ans[id]-=val;
            else ans[id]+=val;
            //if (id==2) cout<<i<<" "<<T[id].q<<" "<<val<<'\n';
        }
    }
    FOR(i,1,m) cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 79196 KB Output is correct
2 Correct 11 ms 79196 KB Output is correct
3 Correct 11 ms 79196 KB Output is correct
4 Correct 11 ms 79196 KB Output is correct
5 Correct 12 ms 79192 KB Output is correct
6 Correct 11 ms 79196 KB Output is correct
7 Correct 12 ms 79416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98132 KB Output is correct
2 Correct 44 ms 98132 KB Output is correct
3 Correct 68 ms 112324 KB Output is correct
4 Correct 65 ms 110420 KB Output is correct
5 Correct 59 ms 110164 KB Output is correct
6 Correct 61 ms 110468 KB Output is correct
7 Correct 41 ms 85332 KB Output is correct
8 Correct 67 ms 101664 KB Output is correct
9 Correct 59 ms 98644 KB Output is correct
10 Correct 43 ms 95828 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 80736 KB Output is correct
2 Correct 25 ms 80472 KB Output is correct
3 Correct 28 ms 80564 KB Output is correct
4 Correct 23 ms 80480 KB Output is correct
5 Correct 29 ms 80476 KB Output is correct
6 Correct 29 ms 80484 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 79196 KB Output is correct
2 Correct 11 ms 79196 KB Output is correct
3 Correct 11 ms 79196 KB Output is correct
4 Correct 11 ms 79196 KB Output is correct
5 Correct 12 ms 79192 KB Output is correct
6 Correct 11 ms 79196 KB Output is correct
7 Correct 12 ms 79416 KB Output is correct
8 Correct 38 ms 98132 KB Output is correct
9 Correct 44 ms 98132 KB Output is correct
10 Correct 68 ms 112324 KB Output is correct
11 Correct 65 ms 110420 KB Output is correct
12 Correct 59 ms 110164 KB Output is correct
13 Correct 61 ms 110468 KB Output is correct
14 Correct 41 ms 85332 KB Output is correct
15 Correct 67 ms 101664 KB Output is correct
16 Correct 59 ms 98644 KB Output is correct
17 Correct 43 ms 95828 KB Output is correct
18 Correct 29 ms 80736 KB Output is correct
19 Correct 25 ms 80472 KB Output is correct
20 Correct 28 ms 80564 KB Output is correct
21 Correct 23 ms 80480 KB Output is correct
22 Correct 29 ms 80476 KB Output is correct
23 Correct 29 ms 80484 KB Output is correct
24 Correct 51 ms 96812 KB Output is correct
25 Correct 63 ms 97876 KB Output is correct
26 Correct 50 ms 96340 KB Output is correct
27 Correct 70 ms 108880 KB Output is correct
28 Correct 94 ms 89684 KB Output is correct
29 Correct 64 ms 82004 KB Output is correct