oj.uz

답안 #1079060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079060 2024-08-28T10:12:47 Z alexander707070 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 211 ms 336984 KB 
#include<bits/stdc++.h>
#define MAXN 100007
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[2000007],suffix[2000007];
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[MAXN],maxs[MAXN];
int from[MAXN],to[MAXN];

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[MAXN];

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:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int f=0;f<s.size();f++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findpref(std::string)':
selling_rna.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int findsuff(std::string)':
selling_rna.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 162436 KB Output is correct
2 Correct 79 ms 162388 KB Output is correct
3 Correct 74 ms 162388 KB Output is correct
4 Correct 89 ms 162384 KB Output is correct
5 Correct 70 ms 162388 KB Output is correct
6 Correct 69 ms 162384 KB Output is correct
7 Correct 70 ms 162384 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 211 ms 336984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 165956 KB Output is correct
2 Correct 83 ms 164692 KB Output is correct
3 Correct 87 ms 165320 KB Output is correct
4 Correct 81 ms 164900 KB Output is correct
5 Correct 83 ms 165172 KB Output is correct
6 Correct 83 ms 165548 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 162436 KB Output is correct
2 Correct 79 ms 162388 KB Output is correct
3 Correct 74 ms 162388 KB Output is correct
4 Correct 89 ms 162384 KB Output is correct
5 Correct 70 ms 162388 KB Output is correct
6 Correct 69 ms 162384 KB Output is correct
7 Correct 70 ms 162384 KB Output is correct
8 Runtime error 211 ms 336984 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -