oj.uz

Submission #1079062

# Submission time Handle Problem Language Result Execution time Memory
1079062 2024-08-28T10:14:22 Z alexander707070 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 196 ms 230680 KB 
#include<bits/stdc++.h>
#define MAXN 100007
#define MAXS 2000007
using namespace std;

struct event{
    int l,r,id;
};

struct node{
    vector<int> words;
    int ch[4];
};

int n,m;
string word[MAXN],s,t;

node prefix[MAXS],suffix[MAXS];
int pr,sf;

void transform(string &s){
    for(int f=0;f<s.size();f++){
        if(s[f]=='G')s[f]='B';
        if(s[f]=='U')s[f]='D';
    }
}

void add(string s,int id){
    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0){
            pr++; prefix[curr].ch[s[i]-'A']=pr;
        }

        curr=prefix[curr].ch[s[i]-'A'];
    }

    prefix[curr].words.push_back(id);

    reverse(s.begin(),s.end());

    curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0){
            sf++; suffix[curr].ch[s[i]-'A']=sf;
        }

        curr=suffix[curr].ch[s[i]-'A'];
    }

    suffix[curr].words.push_back(id);
}

int num,in[MAXN],ans[MAXN];
int euler[MAXN],pos;

int mins[MAXS],maxs[MAXS];
int from[MAXS],to[MAXS];

void dfs(int x){
    mins[x]=num+1;

    for(int i:prefix[x].words){
        num++; in[i]=num;
    }

    for(int i=0;i<4;i++){
        if(prefix[x].ch[i]!=0)dfs(prefix[x].ch[i]);
    }

    maxs[x]=num;
}

void dfs2(int x){
    from[x]=pos+1;

    for(int i:suffix[x].words){
        pos++; euler[pos]=in[i];
    }

    for(int i=0;i<4;i++){
        if(suffix[x].ch[i]!=0)dfs2(suffix[x].ch[i]);
    }

    to[x]=pos;
}


int findpref(string s){
    int curr=0;
    for(int i=0;i<s.size();i++){
        if(prefix[curr].ch[s[i]-'A']==0)return -1;
        curr=prefix[curr].ch[s[i]-'A'];
    }
    
    return curr;
}

int findsuff(string s){
    reverse(s.begin(),s.end());

    int curr=0;
    for(int i=0;i<s.size();i++){
        if(suffix[curr].ch[s[i]-'A']==0)return -1;
        curr=suffix[curr].ch[s[i]-'A'];
    }

    return curr;
}

vector<event> query[MAXS];

int fenwick[MAXN];

void update(int x){
    while(x<=n){
        fenwick[x]++;
        x+=(x & (-x));
    }
}

int getsum(int x){
    int res=0;

    while(x>=1){
        res+=fenwick[x];
        x-=(x & (-x));
    }

    return res;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>word[i];

        transform(word[i]);

        add(word[i],i);
    }

    dfs(0);
    dfs2(0);

    for(int i=1;i<=m;i++){
        cin>>s>>t;

        transform(s);
        transform(t);

        int a=findpref(s);
        int b=findsuff(t);

        if(a==-1 or b==-1)continue;
        if(mins[a]>maxs[a] or from[b]>to[b])continue;

        query[from[b]-1].push_back({mins[a],maxs[a],-i});
        query[to[b]].push_back({mins[a],maxs[a],i});
    }

    for(int i=1;i<=pos;i++){
        update(euler[i]);

        for(event e:query[i]){
            if(e.id<0){
                ans[-e.id]-=getsum(e.r)-getsum(e.l-1);
            }else{
                ans[e.id]+=getsum(e.r)-getsum(e.l-1);
            }
        }
    }

    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'void transform(std::string&)':
selling_rna.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int f=0;f<s.size();f++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findpref(std::string)':
selling_rna.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findsuff(std::string)':
selling_rna.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 207016 KB Output is correct
2 Correct 87 ms 206928 KB Output is correct
3 Correct 86 ms 207112 KB Output is correct
4 Correct 88 ms 207120 KB Output is correct
5 Correct 88 ms 206996 KB Output is correct
6 Correct 94 ms 207064 KB Output is correct
7 Correct 89 ms 206932 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 228948 KB Output is correct
2 Correct 150 ms 228176 KB Output is correct
3 Correct 155 ms 228692 KB Output is correct
4 Correct 156 ms 228436 KB Output is correct
5 Correct 195 ms 230396 KB Output is correct
6 Correct 196 ms 230680 KB Output is correct
7 Correct 130 ms 214416 KB Output is correct
8 Correct 168 ms 226824 KB Output is correct
9 Correct 160 ms 224848 KB Output is correct
10 Correct 139 ms 222036 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 210620 KB Output is correct
2 Correct 103 ms 209472 KB Output is correct
3 Correct 103 ms 209992 KB Output is correct
4 Correct 112 ms 209680 KB Output is correct
5 Correct 102 ms 209548 KB Output is correct
6 Correct 117 ms 210120 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 207016 KB Output is correct
2 Correct 87 ms 206928 KB Output is correct
3 Correct 86 ms 207112 KB Output is correct
4 Correct 88 ms 207120 KB Output is correct
5 Correct 88 ms 206996 KB Output is correct
6 Correct 94 ms 207064 KB Output is correct
7 Correct 89 ms 206932 KB Output is correct
8 Correct 162 ms 228948 KB Output is correct
9 Correct 150 ms 228176 KB Output is correct
10 Correct 155 ms 228692 KB Output is correct
11 Correct 156 ms 228436 KB Output is correct
12 Correct 195 ms 230396 KB Output is correct
13 Correct 196 ms 230680 KB Output is correct
14 Correct 130 ms 214416 KB Output is correct
15 Correct 168 ms 226824 KB Output is correct
16 Correct 160 ms 224848 KB Output is correct
17 Correct 139 ms 222036 KB Output is correct
18 Correct 107 ms 210620 KB Output is correct
19 Correct 103 ms 209472 KB Output is correct
20 Correct 103 ms 209992 KB Output is correct
21 Correct 112 ms 209680 KB Output is correct
22 Correct 102 ms 209548 KB Output is correct
23 Correct 117 ms 210120 KB Output is correct
24 Correct 153 ms 226948 KB Output is correct
25 Correct 152 ms 228684 KB Output is correct
26 Correct 163 ms 226764 KB Output is correct
27 Correct 155 ms 226980 KB Output is correct
28 Correct 179 ms 222412 KB Output is correct
29 Correct 137 ms 216148 KB Output is correct