답안 #1079061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079061	2024-08-28T10:14:00 Z	alexander707070	Selling RNA Strands (JOI16_selling_rna)	C++14	컴파일 오류	0 ms	0 KB

selling_rna

#include<bits/stdc++.h>
#define MAXN 100007
#define MAXN 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:3: warning: "MAXN" redefined
    3 | #define MAXN 2000007
      | 
selling_rna.cpp:2: note: this is the location of the previous definition
    2 | #define MAXN 100007
      | 
selling_rna.cpp:18:13: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   18 | node prefix[MAXS],suffix[MAXS];
      |             ^~~~
      |             MAXN
selling_rna.cpp:18:26: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   18 | node prefix[MAXS],suffix[MAXS];
      |                          ^~~~
      |                          MAXN
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:31:12: error: 'prefix' was not declared in this scope
   31 |         if(prefix[curr].ch[s[i]-'A']==0){
      |            ^~~~~~
selling_rna.cpp:35:14: error: 'prefix' was not declared in this scope
   35 |         curr=prefix[curr].ch[s[i]-'A'];
      |              ^~~~~~
selling_rna.cpp:38:5: error: 'prefix' was not declared in this scope
   38 |     prefix[curr].words.push_back(id);
      |     ^~~~~~
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:44:12: error: 'suffix' was not declared in this scope
   44 |         if(suffix[curr].ch[s[i]-'A']==0){
      |            ^~~~~~
selling_rna.cpp:48:14: error: 'suffix' was not declared in this scope
   48 |         curr=suffix[curr].ch[s[i]-'A'];
      |              ^~~~~~
selling_rna.cpp:51:5: error: 'suffix' was not declared in this scope
   51 |     suffix[curr].words.push_back(id);
      |     ^~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:57:10: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   57 | int mins[MAXS],maxs[MAXS];
      |          ^~~~
      |          MAXN
selling_rna.cpp:57:21: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   57 | int mins[MAXS],maxs[MAXS];
      |                     ^~~~
      |                     MAXN
selling_rna.cpp:58:10: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   58 | int from[MAXS],to[MAXS];
      |          ^~~~
      |          MAXN
selling_rna.cpp:58:19: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
   58 | int from[MAXS],to[MAXS];
      |                   ^~~~
      |                   MAXN
selling_rna.cpp: In function 'void dfs(int)':
selling_rna.cpp:61:5: error: 'mins' was not declared in this scope
   61 |     mins[x]=num+1;
      |     ^~~~
selling_rna.cpp:63:15: error: 'prefix' was not declared in this scope
   63 |     for(int i:prefix[x].words){
      |               ^~~~~~
selling_rna.cpp:68:12: error: 'prefix' was not declared in this scope
   68 |         if(prefix[x].ch[i]!=0)dfs(prefix[x].ch[i]);
      |            ^~~~~~
selling_rna.cpp:71:5: error: 'maxs' was not declared in this scope
   71 |     maxs[x]=num;
      |     ^~~~
selling_rna.cpp: In function 'void dfs2(int)':
selling_rna.cpp:75:5: error: 'from' was not declared in this scope
   75 |     from[x]=pos+1;
      |     ^~~~
selling_rna.cpp:77:15: error: 'suffix' was not declared in this scope
   77 |     for(int i:suffix[x].words){
      |               ^~~~~~
selling_rna.cpp:82:12: error: 'suffix' was not declared in this scope
   82 |         if(suffix[x].ch[i]!=0)dfs2(suffix[x].ch[i]);
      |            ^~~~~~
selling_rna.cpp:85:5: error: 'to' was not declared in this scope; did you mean 't'?
   85 |     to[x]=pos;
      |     ^~
      |     t
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:92:12: error: 'prefix' was not declared in this scope
   92 |         if(prefix[curr].ch[s[i]-'A']==0)return -1;
      |            ^~~~~~
selling_rna.cpp:93:14: error: 'prefix' was not declared in this scope
   93 |         curr=prefix[curr].ch[s[i]-'A'];
      |              ^~~~~~
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++){
      |                 ~^~~~~~~~~
selling_rna.cpp:104:12: error: 'suffix' was not declared in this scope
  104 |         if(suffix[curr].ch[s[i]-'A']==0)return -1;
      |            ^~~~~~
selling_rna.cpp:105:14: error: 'suffix' was not declared in this scope
  105 |         curr=suffix[curr].ch[s[i]-'A'];
      |              ^~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:111:21: error: 'MAXS' was not declared in this scope; did you mean 'MAXN'?
  111 | vector<event> query[MAXS];
      |                     ^~~~
      |                     MAXN
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:161:12: error: 'mins' was not declared in this scope
  161 |         if(mins[a]>maxs[a] or from[b]>to[b])continue;
      |            ^~~~
selling_rna.cpp:161:20: error: 'maxs' was not declared in this scope
  161 |         if(mins[a]>maxs[a] or from[b]>to[b])continue;
      |                    ^~~~
selling_rna.cpp:161:31: error: 'from' was not declared in this scope
  161 |         if(mins[a]>maxs[a] or from[b]>to[b])continue;
      |                               ^~~~
selling_rna.cpp:161:39: error: 'to' was not declared in this scope; did you mean 't'?
  161 |         if(mins[a]>maxs[a] or from[b]>to[b])continue;
      |                                       ^~
      |                                       t
selling_rna.cpp:163:9: error: 'query' was not declared in this scope
  163 |         query[from[b]-1].push_back({mins[a],maxs[a],-i});
      |         ^~~~~
selling_rna.cpp:163:15: error: 'from' was not declared in this scope
  163 |         query[from[b]-1].push_back({mins[a],maxs[a],-i});
      |               ^~~~
selling_rna.cpp:163:37: error: 'mins' was not declared in this scope
  163 |         query[from[b]-1].push_back({mins[a],maxs[a],-i});
      |                                     ^~~~
selling_rna.cpp:163:45: error: 'maxs' was not declared in this scope
  163 |         query[from[b]-1].push_back({mins[a],maxs[a],-i});
      |                                             ^~~~
selling_rna.cpp:164:15: error: 'to' was not declared in this scope; did you mean 't'?
  164 |         query[to[b]].push_back({mins[a],maxs[a],i});
      |               ^~
      |               t
selling_rna.cpp:170:21: error: 'query' was not declared in this scope
  170 |         for(event e:query[i]){
      |                     ^~~~~