oj.uz

Submission #1106555

# Submission time Handle Problem Language Result Execution time Memory
1106555 2024-10-30T16:16:06 Z ntdaccode Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 88 ms 85576 KB 
#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=222000;
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;
  int sz=s.size()-1;
  fori(i,0,sz) {
    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;
  int sz=s.size()-1;
  fori(i,0,sz) {
    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;
  int sz=s.size()-1;
  fori(i,0,sz) {
    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;
  int sz=s.size()-1;
  fori(i,0,sz) {
    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";
  }


}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10884 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 2 ms 11000 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 85576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11856 KB Output is correct
2 Correct 15 ms 11728 KB Output is correct
3 Correct 20 ms 11600 KB Output is correct
4 Correct 13 ms 11600 KB Output is correct
5 Correct 15 ms 11856 KB Output is correct
6 Correct 18 ms 11856 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10884 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 3 ms 10832 KB Output is correct
6 Correct 2 ms 11000 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct
8 Runtime error 88 ms 85576 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -