oj.uz

Submission #668184

# Submission time Handle Problem Language Result Execution time Memory
668184 2022-12-03T08:19:15 Z Ninja_Kunai Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 380 ms 552148 KB 
/**
*    Author :  Nguyen Tuan Vu
*    Created : 02.12.2022
**/
 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
 
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}
 
using namespace std;
 
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
 
void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}
 
const int N = 1e5 + 5;
int n, nquery;
string s[N];
 
namespace sub2 {
    struct TRIE {
        struct node {
            node *child[26];
            vector <int> S;
 
            node() {
                REP(i, 26) child[i] = NULL;
            }
        } *root;
 
        TRIE() {
            root = new node();
        }
 
        void add(string &x, int ID) {
            node *p = root;
            for (auto c : x) {
                if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
                p = p -> child[c - 'A'];
                p -> S.push_back(ID - 1);
            }
        }
 
        vector <int> get(string &x) {
            node *p = root;
            for (auto c : x) {
                if (p -> child[c - 'A'] == NULL) return vector <int> ();
                p = p -> child[c - 'A'];
            }
 
            return p -> S;
        }
    } trie[2];

    const int base = 31;
    const int Mod = 1e9 + 7;
    vector <int> Hash[N];
    int Pow[N], ID[N];
 
    int getHash(int i, int l, int r) {
        return (Hash[i][r] - 1ll * Hash[i][l - 1] * Pow[r - l + 1] % Mod + Mod) % Mod;
    }

    void solve() {
        FOR(i, 1, n) {
            Hash[i].resize(s[i].size() + 5, 0);
            REP(j, s[i].size()) Hash[i][j + 1] = (1ll * Hash[i][j] * base % Mod + s[i][j] - 'A' + 1) % Mod;
        }
 
        Pow[0] = 1;
        FOR(i, 1, 1e5) Pow[i] = 1ll * Pow[i - 1] * base % Mod;
        FOR(i, 1, n) ID[i] = i;
        sort (ID + 1, ID + n + 1, [] (int &x, int &y) {
            int l = -1, r = min((int) s[x].size(), (int) s[y].size()) + 1;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (getHash(x, 1, mid) == getHash(y, 1, mid)) l = mid;
                else r = mid;
            }
 
            if (l == min((int) s[x].size(), (int) s[y].size())) {
                return (s[x].size() <= s[y].size());
            }
 
            return (s[x][l] <= s[y][l]);
        });
                
        FOR(i, 1, n) {
            trie[0].add(s[i], i);
            reverse(ALL(s[i]));
            trie[1].add(s[i], i);
        }
 
        while (nquery--) {
            string PREF, SUFF;
            cin >> PREF >> SUFF;
 
            reverse(ALL(SUFF));
            vector <int> Pref = trie[0].get(PREF);
            vector <int> Suff = trie[1].get(SUFF);
            int ans = 0;
            int j = -1;
            REP(i, Pref.size()) {
                while (j < (int) Suff.size() - 1 && Suff[j + 1] < Pref[i]) {
                    ++j;
                }
 
                if (j == (int) Suff.size() - 1) break;
                if (Suff[j + 1] == Pref[i]) ++ans;
            }
 
            cout << ans << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
 
    cin >> n >> nquery;
    FOR(i, 1, n) cin >> s[i];
    sub2::solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

Compilation message

selling_rna.cpp: In function 'void file()':
selling_rna.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6204 KB Output is correct
2 Correct 5 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6200 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 552148 KB Output is correct
2 Runtime error 57 ms 32764 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 17424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6204 KB Output is correct
2 Correct 5 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6200 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 380 ms 552148 KB Output is correct
9 Runtime error 57 ms 32764 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -