Submission #1106538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106538		ntdaccode	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	298 ms	380488 KiB

selling_rna

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=3e6+10;
const int mod=1e9+7;
int n,m;
int ch[N][26],ch2[N][26];
int l[N],r[N];
vector<int> suf[N];
int cnt=0,cnt2=0;
void upd(string s,int node)
{
  int idx=0;
  fori(i,0,s.size()-1) {
    int k=s[i]-'A';
    if(!ch[idx][k])
    {
      ch[idx][k]=++cnt;
      l[cnt]=1e9;
      r[cnt]=0;
    }
    l[idx]=min(l[idx],node);
    r[idx]=max(r[idx],node);
    idx=ch[idx][k];
  }
  l[idx]=min(l[idx],node);
  r[idx]=max(r[idx],node);

}
void upd2(string s,int node)
{
  int idx=0;
  fori(i,0,s.size()-1) {
    int k=s[i]-'A';
    if(!ch2[idx][k]) ch2[idx][k]=++cnt2;
    suf[idx].pb(node);
    idx=ch2[idx][k];
  }
  suf[idx].pb(node);
}
ii get(string s)
{
  int idx=0;
  fori(i,0,s.size()-1) {
    int k=s[i]-'A';
    if(!ch[idx][k]) return {0,0};
    idx=ch[idx][k];
  }
  return {l[idx],r[idx]};
}
int get2(string s,int u,int v)
{
  int idx=0;
  fori(i,0,s.size()-1) {
    int k=s[i]-'A';
    if(!ch2[idx][k]) return 0;
    idx=ch2[idx][k];
    //cout << idx << " " << s[i] << "\n";
  }
  //for(int x:suf[idx]) cout << x << " ";
  int uu=lower_bound(suf[idx].begin(),suf[idx].end(),u)-suf[idx].begin();
  int vv=upper_bound(suf[idx].begin(),suf[idx].end(),v)-suf[idx].begin();
  return vv-uu;
}
string s[M];
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n >> m;
  fori(i,1,n) cin >> s[i];
  l[0]=1e9,r[0]=0;
  sort(s+1,s+n+1);
  fori(i,1,n){
    upd(s[i],i);
    reverse(s[i].begin(),s[i].end());
    upd2(s[i],i);
  }
  while(m--) {
    string pre,suf;
    cin >> pre >> suf;
    reverse(suf.begin(),suf.end());
    auto [u,v] = get(pre);
    if(u==0&&v==0) cout << 0 << "\n";
    else cout << get2(suf,u,v) << "\n";
  }


}

Compilation message (stderr)

selling_rna.cpp: In function 'void upd(std::string, int)':
selling_rna.cpp:2:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define fori(i,a,b) for(int i=a;i<=b;i++)
......
   19 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:19:3: note: in expansion of macro 'fori'
   19 |   fori(i,0,s.size()-1) {
      |   ^~~~
selling_rna.cpp: In function 'void upd2(std::string, int)':
selling_rna.cpp:2:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define fori(i,a,b) for(int i=a;i<=b;i++)
......
   38 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:38:3: note: in expansion of macro 'fori'
   38 |   fori(i,0,s.size()-1) {
      |   ^~~~
selling_rna.cpp: In function 'ii get(std::string)':
selling_rna.cpp:2:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define fori(i,a,b) for(int i=a;i<=b;i++)
......
   49 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:49:3: note: in expansion of macro 'fori'
   49 |   fori(i,0,s.size()-1) {
      |   ^~~~
selling_rna.cpp: In function 'int get2(std::string, int, int)':
selling_rna.cpp:2:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define fori(i,a,b) for(int i=a;i<=b;i++)
......
   59 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:59:3: note: in expansion of macro 'fori'
   59 |   fori(i,0,s.size()-1) {
      |   ^~~~
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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