oj.uz

Submission #668187

# Submission time Handle Problem Language Result Execution time Memory
668187 2022-12-03T08:23:53 Z Ninja_Kunai Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 563 ms 670192 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 = 0, 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 5 ms 6228 KB Output is correct
2 Correct 4 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6152 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 552104 KB Output is correct
2 Correct 401 ms 523776 KB Output is correct
3 Correct 386 ms 544860 KB Output is correct
4 Correct 381 ms 519156 KB Output is correct
5 Correct 563 ms 660772 KB Output is correct
6 Correct 485 ms 670192 KB Output is correct
7 Correct 182 ms 31876 KB Output is correct
8 Correct 356 ms 408456 KB Output is correct
9 Correct 333 ms 345784 KB Output is correct
10 Correct 343 ms 337096 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 17704 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 5 ms 6228 KB Output is correct
2 Correct 4 ms 6228 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 4 ms 6152 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 374 ms 552104 KB Output is correct
9 Correct 401 ms 523776 KB Output is correct
10 Correct 386 ms 544860 KB Output is correct
11 Correct 381 ms 519156 KB Output is correct
12 Correct 563 ms 660772 KB Output is correct
13 Correct 485 ms 670192 KB Output is correct
14 Correct 182 ms 31876 KB Output is correct
15 Correct 356 ms 408456 KB Output is correct
16 Correct 333 ms 345784 KB Output is correct
17 Correct 343 ms 337096 KB Output is correct
18 Runtime error 20 ms 17704 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -