oj.uz

Submission #856976

# Submission time Handle Problem Language Result Execution time Memory
856976 2023-10-05T03:02:11 Z TS_2392 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 105 ms 112128 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 79344 KB Output is correct
4 Correct 11 ms 79196 KB Output is correct
5 Correct 11 ms 79196 KB Output is correct
6 Correct 11 ms 79196 KB Output is correct
7 Correct 11 ms 79192 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98064 KB Output is correct
2 Correct 45 ms 98056 KB Output is correct
3 Correct 69 ms 112128 KB Output is correct
4 Correct 66 ms 110548 KB Output is correct
5 Correct 61 ms 110260 KB Output is correct
6 Correct 61 ms 110228 KB Output is correct
7 Correct 41 ms 85332 KB Output is correct
8 Correct 67 ms 101456 KB Output is correct
9 Correct 61 ms 98584 KB Output is correct
10 Correct 44 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 24 ms 80476 KB Output is correct
3 Correct 28 ms 80660 KB Output is correct
4 Correct 24 ms 80728 KB Output is correct
5 Correct 25 ms 80380 KB Output is correct
6 Correct 28 ms 80476 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 79344 KB Output is correct
4 Correct 11 ms 79196 KB Output is correct
5 Correct 11 ms 79196 KB Output is correct
6 Correct 11 ms 79196 KB Output is correct
7 Correct 11 ms 79192 KB Output is correct
8 Correct 41 ms 98064 KB Output is correct
9 Correct 45 ms 98056 KB Output is correct
10 Correct 69 ms 112128 KB Output is correct
11 Correct 66 ms 110548 KB Output is correct
12 Correct 61 ms 110260 KB Output is correct
13 Correct 61 ms 110228 KB Output is correct
14 Correct 41 ms 85332 KB Output is correct
15 Correct 67 ms 101456 KB Output is correct
16 Correct 61 ms 98584 KB Output is correct
17 Correct 44 ms 95828 KB Output is correct
18 Correct 29 ms 80736 KB Output is correct
19 Correct 24 ms 80476 KB Output is correct
20 Correct 28 ms 80660 KB Output is correct
21 Correct 24 ms 80728 KB Output is correct
22 Correct 25 ms 80380 KB Output is correct
23 Correct 28 ms 80476 KB Output is correct
24 Correct 51 ms 96852 KB Output is correct
25 Correct 62 ms 97780 KB Output is correct
26 Correct 49 ms 96208 KB Output is correct
27 Correct 75 ms 108880 KB Output is correct
28 Correct 105 ms 89696 KB Output is correct
29 Correct 62 ms 81888 KB Output is correct