Submission #263141

#	Time	Username	Problem	Language	Result	Execution time	Memory
263141		sckmd	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1354 ms	1048580 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
typedef pair<int,int> pii;
vector <string> v;

struct node
{
  node* a;
  node* c;
  node* g;
  node* u;
  int cnt = 0;
  int leafshere = 0;
};
node* root1;
node* root2;
void add1(node* root,string s)
{
  node* now = root;
  now->cnt++;
  //acgu lexicograph
  for(int i = 0; i < s.length(); i++)
  {
    if(s[i]=='A')
    {
      if(now->a == NULL)now->a=new node();
      now=now->a;
    }
    if(s[i]=='C')
    {
      if(now->c == NULL)now->c=new node();
      now=now->c;
    }
    if(s[i]=='G')
    {
      if(now->g == NULL)now->g=new node();
      now=now->g;
    }
    if(s[i]=='U')
    {
      if(now->u == NULL)now->u=new node();
      now=now->u;
    }
    now->cnt++;
  }
  now->leafshere++;
}
string extract1(node* root)
{
  node* now = root;
  string ret = "";
  now->cnt--;
  while(1)
  {
    if(now->leafshere > 0){now->leafshere-=1;break;}
    if(now->a != NULL && now->a->cnt > 0){now=now->a;now->cnt -= 1;ret += 'A';continue;}
    if(now->c != NULL && now->c->cnt > 0){now=now->c;now->cnt -= 1;ret += 'C';continue;}
    if(now->g != NULL && now->g->cnt > 0){now=now->g;now->cnt -= 1;ret += 'G';continue;}
    if(now->u != NULL && now->u->cnt > 0){now=now->u;now->cnt -= 1;ret += 'U';continue;}
    break;
  }
  return ret;
}

node* tree[MAXN*4];

int query1(node* root,string tar)
{
  node* now = root;
  for(int i = 0; i < tar.length(); i++)
  {
    if(tar[i]=='A')
    {
      if(now->a == NULL || now->a->cnt == 0)return 0;
      now = now->a;
    }
    if(tar[i]=='C')
    {
      if(now->c == NULL || now->c->cnt == 0)return 0;
      now = now->c;
    }
    if(tar[i]=='G')
    {
      if(now->g == NULL || now->g->cnt == 0)return 0;
      now = now->g;
    }
    if(tar[i]=='U')
    {
      if(now->u == NULL || now->u->cnt == 0)return 0;
      now = now->u;
    }
  }
  return now->cnt;
}

void build(int id,int l,int r)
{
  tree[id]=new node();
  for(int j = l; j <= r; j++)
  {
    string z = v[j];
    reverse(z.begin(),z.end());
    add1(tree[id],z);
  }
  if(l==r)
  {
    return ;
  }
  int mid=l+r>>1;
  build(id*2,l,mid);
  build(id*2+1,mid+1,r);
}
int query(int id,int left,int right,int l,int r,string target)
{
  if(left > right || l > right || left > r)return 0;
  if(left >= l && right <= r)
  {
    //cout << id << " " << left << " " << right << " " << l << " " << r << " " << target << "\n";
    return query1(tree[id],target);
  }
  int mid=left+right>>1;
  return query(id*2,left,mid,l,r,target)+query(id*2+1,mid+1,right,l,r,target);
}
pii findbounds(string s)
{
  node* now = root2;
  int pos = 0;
  for(int i = 0; i < s.length(); i++)
  {
    if(s[i]=='A')
    {
      if(now->a == NULL || now->a->cnt == 0)return make_pair(-1,-1);
      now=now->a;
    }
    if(s[i]=='C')
    {
      if(now->c == NULL || now->c->cnt == 0)return make_pair(-1,-1);
      if(now->a != NULL)pos += now->a->cnt;
      now=now->c;
    }
    if(s[i]=='G')
    {
      if(now->g == NULL || now->g->cnt == 0)return make_pair(-1,-1);
      if(now->a != NULL)pos += now->a->cnt;
      if(now->c != NULL)pos += now->c->cnt;
      now=now->g;
    }
    if(s[i]=='U')
    {
      if(now->u == NULL || now->u->cnt == 0)return make_pair(-1,-1);
      if(now->a != NULL)pos += now->a->cnt;
      if(now->c != NULL)pos += now->c->cnt;
      if(now->g != NULL)pos += now->g->cnt;
      now=now->u;
    }
  }
  return {pos,pos+now->cnt-1};
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,m;
  cin >> n >> m;
  root1 = new node();
  root2 = new node();
  for(int i = 0; i < n; i++)
  {
    string s;
    cin >> s;
    add1(root1,s);
    add1(root2,s);
  }
  for(int i = 0; i < n; i++)
  {
    v.push_back(extract1(root1));
  }
  build(1,0,n-1);
  while(m--)
  {
    string s,t;
    cin >> s >> t;
    pii bounds = findbounds(s);
    if(bounds == make_pair(-1,-1)){cout << "0\n";continue;}
    if(bounds.first < 0 || bounds.second >= n || bounds.first >= n || bounds.second < 0 || bounds.first > bounds.second){cout << "0\n";continue;}
    cout << query(1,0,n-1,bounds.first,bounds.second,t) << "\n";
  }
  //for(int i = 0; i < n; i++)cout << extract1(tree[1]) << "\n";
  return 0;
}
/*
2 3
AUGC
AGC
G C
AU C
A C
*/

Compilation message (stderr)

selling_rna.cpp: In function 'void add1(node*, std::string)':
selling_rna.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i = 0; i < s.length(); i++)
      |                  ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int query1(node*, std::string)':
selling_rna.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i < tar.length(); i++)
      |                  ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void build(int, int, int)':
selling_rna.cpp:111:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |   int mid=l+r>>1;
      |           ~^~
selling_rna.cpp: In function 'int query(int, int, int, int, int, std::string)':
selling_rna.cpp:123:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |   int mid=left+right>>1;
      |           ~~~~^~~~~~
selling_rna.cpp: In function 'pii findbounds(std::string)':
selling_rna.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int i = 0; i < s.length(); i++)
      |                  ~~^~~~~~~~~~~~

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