oj.uz

Submission #668183

# Submission time Handle Problem Language Result Execution time Memory
668183 2022-12-03T08:15:00 Z Ninja_Kunai Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 670120 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;
        }
        		
		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 4 ms 5844 KB Output is correct
2 Correct 4 ms 5812 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5808 KB Output is correct
7 Correct 4 ms 5808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 551788 KB Output is correct
2 Correct 439 ms 523316 KB Output is correct
3 Correct 402 ms 544436 KB Output is correct
4 Correct 410 ms 518804 KB Output is correct
5 Correct 542 ms 660280 KB Output is correct
6 Correct 553 ms 670120 KB Output is correct
7 Correct 170 ms 31712 KB Output is correct
8 Correct 375 ms 408144 KB Output is correct
9 Correct 334 ms 345492 KB Output is correct
10 Correct 371 ms 336904 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 9756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 4 ms 5812 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5808 KB Output is correct
7 Correct 4 ms 5808 KB Output is correct
8 Correct 478 ms 551788 KB Output is correct
9 Correct 439 ms 523316 KB Output is correct
10 Correct 402 ms 544436 KB Output is correct
11 Correct 410 ms 518804 KB Output is correct
12 Correct 542 ms 660280 KB Output is correct
13 Correct 553 ms 670120 KB Output is correct
14 Correct 170 ms 31712 KB Output is correct
15 Correct 375 ms 408144 KB Output is correct
16 Correct 334 ms 345492 KB Output is correct
17 Correct 371 ms 336904 KB Output is correct
18 Execution timed out 1571 ms 9756 KB Time limit exceeded
19 Halted 0 ms 0 KB -