제출 #1106545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106545		ntdaccode	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	270 ms	354892 KiB

selling_rna

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

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=2e6+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;
    }
    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;
    idx=ch2[idx][k];
    suf[idx].push_back(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];
  }
  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];
  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";
  }


}

컴파일 시 표준 에러 (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++)
......
   36 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:36:3: note: in expansion of macro 'fori'
   36 |   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++)
......
   46 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:46:3: note: in expansion of macro 'fori'
   46 |   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++)
......
   56 |   fori(i,0,s.size()-1) {
      |        ~~~~~~~~~~~~~~             
selling_rna.cpp:56:3: note: in expansion of macro 'fori'
   56 |   fori(i,0,s.size()-1) {
      |   ^~~~
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
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(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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