제출 #310277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310277		mohamedsobhi777	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	401 ms	356980 KiB

selling_rna

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 2e6 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n, m; 
string s , t; 
vector<string> lst ; 

int node1, node2 ; 
int nxt[N][26], nxt2[N][26] ; 
vector<int> vec[N] ; 
int L[N] , R[N] ; 
inline void norm(string &x){for(auto &u : x)u -='A';}

void add1(string &x, int j){
        int cur = 0 ; 
        for(int i = 0 ; i < (int) x.size() ; ++ i){
                if(!nxt[cur][ x[i] ])
                        nxt[cur][x[i]] = ++ node1 ; 
                cur = nxt[cur][x[i]] ; 
                L[cur] = min(L[cur] , j) ; 
                R[cur] = max(R[cur] , j) ; 
        }
}

pair<int,int> getlr(string &x){
        int cur = 0 ; 
        for(int i = 0 ;i <(int) x.size() ; ++ i){
                if(!nxt[cur][x[i]])return {-1 , -1} ; 
                cur = nxt[cur][x[i]] ; 
        }
        return {L[cur] , R[cur]} ; 
}


void add2(string &x, int j){
        int cur = 0 ; 
        for(int i = (int) x.size() - 1 ; ~ i ; -- i){
                if(!nxt2[cur][ x[i] ])
                        nxt2[cur][x[i]] = ++ node2 ; 
                cur = nxt2[cur][x[i]] ; 
                vec[cur].push_back(j) ; 
        }
}

int solve(string &x, int l , int r){
        int cur = 0 ; 
        for(int i = (int) x.size() - 1 ; ~ i ; -- i){
                if(!nxt2[cur][ x[i] ])return 0 ; 
                cur = nxt2[cur][x[i]] ;  
        }
        return upper_bound(vec[cur].begin() , vec[cur].end() , r) -
        lower_bound(vec[cur].begin() , vec[cur].end(), l ) ; 
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n >> m; 
        for(int i = 0 ; i < n; ++ i){
                cin >> s; 
                norm(s) ;
                lst.push_back(s) ; 
        }

        sort(lst.begin() , lst.end()) ; 
        for(int i = 0 ;i < N; ++ i)
                L[i] = 1e9, R[i] = -1 ; 

        for(int i = 0 ; i < n ; ++ i){
                add1(lst[i], i) ; 
                add2(lst[i] , i); 
        }
        for(int i = 0 ;i < N; ++ i)sort(vec[i].begin() , vec[i].end()) ;
                for(int i = 0 ;i < m ; ++ i){
                        cin >> s >> t; 
                        norm(s) ; norm(t); 
                        pair<int,int> p = getlr(s) ; 
                        if(p.first == -1){
                                cout<<"0\n" ; 
                                continue ; 
                        }
                        cout<< solve(t , p.first , p.second) <<"\n" ; 
                }

                return 0 ; 
        }

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void add1(std::string&, int)':
selling_rna.cpp:39:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |                 if(!nxt[cur][ x[i] ])
      |                                    ^
selling_rna.cpp:40:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |                         nxt[cur][x[i]] = ++ node1 ;
      |                                      ^
selling_rna.cpp:41:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |                 cur = nxt[cur][x[i]] ;
      |                                    ^
selling_rna.cpp: In function 'std::pair<int, int> getlr(std::string&)':
selling_rna.cpp:50:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 if(!nxt[cur][x[i]])return {-1 , -1} ;
      |                                  ^
selling_rna.cpp:51:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |                 cur = nxt[cur][x[i]] ;
      |                                    ^
selling_rna.cpp: In function 'void add2(std::string&, int)':
selling_rna.cpp:60:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |                 if(!nxt2[cur][ x[i] ])
      |                                     ^
selling_rna.cpp:61:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   61 |                         nxt2[cur][x[i]] = ++ node2 ;
      |                                       ^
selling_rna.cpp:62:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                 cur = nxt2[cur][x[i]] ;
      |                                     ^
selling_rna.cpp: In function 'int solve(std::string&, int, int)':
selling_rna.cpp:70:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |                 if(!nxt2[cur][ x[i] ])return 0 ;
      |                                     ^
selling_rna.cpp:71:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |                 cur = nxt2[cur][x[i]] ;
      |                                     ^

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