oj.uz

Submission #668029

# Submission time Handle Problem Language Result Execution time Memory
668029 2022-12-02T15:13:49 Z Ninja_Kunai Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 664452 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];

	void solve() {
		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 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 545352 KB Output is correct
2 Correct 366 ms 516556 KB Output is correct
3 Correct 351 ms 537448 KB Output is correct
4 Correct 353 ms 511892 KB Output is correct
5 Correct 453 ms 654820 KB Output is correct
6 Correct 607 ms 664452 KB Output is correct
7 Correct 146 ms 28088 KB Output is correct
8 Correct 330 ms 403032 KB Output is correct
9 Correct 292 ms 340244 KB Output is correct
10 Correct 300 ms 329332 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 338 ms 545352 KB Output is correct
9 Correct 366 ms 516556 KB Output is correct
10 Correct 351 ms 537448 KB Output is correct
11 Correct 353 ms 511892 KB Output is correct
12 Correct 453 ms 654820 KB Output is correct
13 Correct 607 ms 664452 KB Output is correct
14 Correct 146 ms 28088 KB Output is correct
15 Correct 330 ms 403032 KB Output is correct
16 Correct 292 ms 340244 KB Output is correct
17 Correct 300 ms 329332 KB Output is correct
18 Execution timed out 1579 ms 4924 KB Time limit exceeded
19 Halted 0 ms 0 KB -