oj.uz

Submission #550161

# Submission time Handle Problem Language Result Execution time Memory
550161 2022-04-17T12:10:22 Z farhan132 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 332 ms 371736 KB 
/***Farhan132***/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast,fast-math")
 
 
#include <bits/stdc++.h>
 
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
 
const ll mod =  (ll) 998244353;
//const ll mod =  (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = (ll)1e18;
 
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
 
bool USACO = 0;
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll N = 2e6 + 5;

ll nxt[2][N][4];
vector < ll > v[2][N];
ll sum[N];

ll lol(char c){
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    return 3;
}
ll id[] = {1, 1};

void add(string s, ll x, ll _i){
    ll cur = 1;
    for(ll i = 0; i < s.size(); i++){
        ll a = lol(s[i]);
        if(nxt[x][cur][a] == -1){
            nxt[x][cur][a] = ++id[x];
        }
        cur = nxt[x][cur][a];
        v[x][cur].pb(_i);
    }
    return;
}
ii query(string s){
    ll x = 0, cur = 1;
    for(ll i = 0; i < s.size(); i++){
        ll a = lol(s[i]);
        if(nxt[x][cur][a] == -1) return {0, 0};
        cur = nxt[x][cur][a];
    }

    return {v[0][cur][0], v[0][cur].back()}; 
}
ll count(string s, ii p){
    ll x = 1, cur = 1;
    for(ll i = 0; i < s.size(); i++){
        ll a = lol(s[i]);
        if(nxt[x][cur][a] == -1) return 0;
        cur = nxt[x][cur][a];
    }

    return upper_bound(v[x][cur].begin(), v[x][cur].end(), p.ss) -  lower_bound(v[x][cur].begin(), v[x][cur].end(), p.ff);
}

string s[N];

void solve(){

  mem(nxt, -1);
  
  ll n , q;
  cin >> n >> q;

  for(ll i = 1; i <= n; i++) cin >> s[i];
  
  sort(s + 1, s + n + 1);

  for(ll i = 1; i <= n; i++){
    add(s[i], 0, i);
    reverse(s[i].begin(), s[i].end());
    add(s[i], 1, i);
  }

  while(q--){
    string p, q;
    cin >> p >> q;
    reverse(q.begin(), q.end());
    cout << count(q, query(p)) << '\n';
  }
  
  return;
}
 
int main() {
    
    
    #ifdef LOCAL
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
        auto start_time = clock();
    #else 
       ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    #endif
 
    //pre(N);
 
    ll T = 1, CT = 0;  //cin >> T; 
 
    while(T--){
       //  cout << "Case #" << ++CT <<": " ;
        solve();
    }
    #ifdef LOCAL
        auto end_time = clock();
        cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n";
    #endif
 
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, ll, ll)':
selling_rna.cpp:83:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(ll i = 0; i < s.size(); i++){
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'ii query(std::string)':
selling_rna.cpp:95:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(ll i = 0; i < s.size(); i++){
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'll count(std::string, ii)':
selling_rna.cpp:105:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(ll i = 0; i < s.size(); i++){
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:156:15: warning: unused variable 'CT' [-Wunused-variable]
  156 |     ll T = 1, CT = 0;  //cin >> T;
      |               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 282100 KB Output is correct
2 Correct 115 ms 282040 KB Output is correct
3 Correct 123 ms 282008 KB Output is correct
4 Correct 138 ms 282092 KB Output is correct
5 Correct 119 ms 282048 KB Output is correct
6 Correct 129 ms 282048 KB Output is correct
7 Correct 121 ms 282136 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 371736 KB Output is correct
2 Correct 295 ms 366908 KB Output is correct
3 Correct 280 ms 369636 KB Output is correct
4 Correct 323 ms 365924 KB Output is correct
5 Correct 275 ms 362644 KB Output is correct
6 Correct 304 ms 363804 KB Output is correct
7 Correct 187 ms 320808 KB Output is correct
8 Correct 332 ms 360152 KB Output is correct
9 Correct 327 ms 353080 KB Output is correct
10 Correct 259 ms 349112 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 284788 KB Output is correct
2 Correct 151 ms 284628 KB Output is correct
3 Correct 143 ms 284640 KB Output is correct
4 Correct 131 ms 284660 KB Output is correct
5 Correct 138 ms 284616 KB Output is correct
6 Correct 153 ms 284552 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 282100 KB Output is correct
2 Correct 115 ms 282040 KB Output is correct
3 Correct 123 ms 282008 KB Output is correct
4 Correct 138 ms 282092 KB Output is correct
5 Correct 119 ms 282048 KB Output is correct
6 Correct 129 ms 282048 KB Output is correct
7 Correct 121 ms 282136 KB Output is correct
8 Correct 323 ms 371736 KB Output is correct
9 Correct 295 ms 366908 KB Output is correct
10 Correct 280 ms 369636 KB Output is correct
11 Correct 323 ms 365924 KB Output is correct
12 Correct 275 ms 362644 KB Output is correct
13 Correct 304 ms 363804 KB Output is correct
14 Correct 187 ms 320808 KB Output is correct
15 Correct 332 ms 360152 KB Output is correct
16 Correct 327 ms 353080 KB Output is correct
17 Correct 259 ms 349112 KB Output is correct
18 Correct 153 ms 284788 KB Output is correct
19 Correct 151 ms 284628 KB Output is correct
20 Correct 143 ms 284640 KB Output is correct
21 Correct 131 ms 284660 KB Output is correct
22 Correct 138 ms 284616 KB Output is correct
23 Correct 153 ms 284552 KB Output is correct
24 Correct 324 ms 359172 KB Output is correct
25 Correct 312 ms 359372 KB Output is correct
26 Correct 313 ms 358464 KB Output is correct
27 Correct 292 ms 357976 KB Output is correct
28 Correct 314 ms 331076 KB Output is correct
29 Correct 198 ms 304140 KB Output is correct