oj.uz

Submission #310277

# Submission time Handle Problem Language Result Execution time Memory
310277 2020-10-06T13:26:05 Z mohamedsobhi777 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 401 ms 356980 KB 
#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. 
*/

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 62968 KB Output is correct
2 Correct 43 ms 63048 KB Output is correct
3 Correct 43 ms 62968 KB Output is correct
4 Correct 42 ms 62968 KB Output is correct
5 Correct 43 ms 62972 KB Output is correct
6 Correct 43 ms 63044 KB Output is correct
7 Correct 44 ms 62980 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 328824 KB Output is correct
2 Correct 398 ms 317172 KB Output is correct
3 Correct 298 ms 278140 KB Output is correct
4 Correct 290 ms 268276 KB Output is correct
5 Correct 369 ms 352628 KB Output is correct
6 Correct 387 ms 356980 KB Output is correct
7 Correct 133 ms 78744 KB Output is correct
8 Correct 372 ms 244596 KB Output is correct
9 Correct 306 ms 216948 KB Output is correct
10 Correct 272 ms 210552 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 65512 KB Output is correct
2 Correct 70 ms 65364 KB Output is correct
3 Correct 75 ms 65384 KB Output is correct
4 Correct 66 ms 64744 KB Output is correct
5 Correct 69 ms 65136 KB Output is correct
6 Correct 75 ms 65228 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 62968 KB Output is correct
2 Correct 43 ms 63048 KB Output is correct
3 Correct 43 ms 62968 KB Output is correct
4 Correct 42 ms 62968 KB Output is correct
5 Correct 43 ms 62972 KB Output is correct
6 Correct 43 ms 63044 KB Output is correct
7 Correct 44 ms 62980 KB Output is correct
8 Correct 401 ms 328824 KB Output is correct
9 Correct 398 ms 317172 KB Output is correct
10 Correct 298 ms 278140 KB Output is correct
11 Correct 290 ms 268276 KB Output is correct
12 Correct 369 ms 352628 KB Output is correct
13 Correct 387 ms 356980 KB Output is correct
14 Correct 133 ms 78744 KB Output is correct
15 Correct 372 ms 244596 KB Output is correct
16 Correct 306 ms 216948 KB Output is correct
17 Correct 272 ms 210552 KB Output is correct
18 Correct 75 ms 65512 KB Output is correct
19 Correct 70 ms 65364 KB Output is correct
20 Correct 75 ms 65384 KB Output is correct
21 Correct 66 ms 64744 KB Output is correct
22 Correct 69 ms 65136 KB Output is correct
23 Correct 75 ms 65228 KB Output is correct
24 Correct 365 ms 283504 KB Output is correct
25 Correct 370 ms 283640 KB Output is correct
26 Correct 386 ms 280944 KB Output is correct
27 Correct 283 ms 241312 KB Output is correct
28 Correct 285 ms 109404 KB Output is correct
29 Correct 154 ms 74848 KB Output is correct