Submission #856967

#	Time	Username	Problem	Language	Result	Execution time	Memory
856967		TS_2392	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	37 ms	99924 KiB

selling_rna

#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][c]) Trie[u][c]=++cnt;
        u=Trie[u][c];
        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][c]) return {0,0};
        u=Trie[u][c];
    }
    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][c]) Trie[u][c]=++cnt;
        u=Trie[u][c];
        ++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][c]) return 0;
        u=Trie[u][c];
    }
    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,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));
    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<<T[id].q<<" "<<val<<'\n';
        }
    }
    FOR(i,1,m) cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void Add(std::string, long long int)':
selling_rna.cpp:31:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         if (!Trie[u][c]) Trie[u][c]=++cnt;
      |                      ^
selling_rna.cpp:31:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         if (!Trie[u][c]) Trie[u][c]=++cnt;
      |                                  ^
selling_rna.cpp:32:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |         u=Trie[u][c];
      |                   ^
selling_rna.cpp:25:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   25 |         int x=0;
      |             ^
selling_rna.cpp: In function 'std::pair<long long int, long long int> Get(std::string)':
selling_rna.cpp:46:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |         if (!Trie[u][c]) return {0,0};
      |                      ^
selling_rna.cpp:47:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |         u=Trie[u][c];
      |                   ^
selling_rna.cpp:40:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   40 |         int x=0;
      |             ^
selling_rna.cpp: In function 'void Add2(std::string)':
selling_rna.cpp:62:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |         if (!Trie[u][c]) Trie[u][c]=++cnt;
      |                      ^
selling_rna.cpp:62:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |         if (!Trie[u][c]) Trie[u][c]=++cnt;
      |                                  ^
selling_rna.cpp:63:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |         u=Trie[u][c];
      |                   ^
selling_rna.cpp:56:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   56 |         int x=0;
      |             ^
selling_rna.cpp: In function 'long long int Get2(std::string)':
selling_rna.cpp:76:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |         if (!Trie[u][c]) return 0;
      |                      ^
selling_rna.cpp:77:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |         u=Trie[u][c];
      |                   ^
selling_rna.cpp:70:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   70 |         int x=0;
      |             ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40