# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
848298 | 2023-09-12T03:13:40 Z | quandlm | Selling RNA Strands (JOI16_selling_rna) | C++17 | 385 ms | 666028 KB |
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); } #define ll long long #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define REP(i, a, b) for (int i = (a); i >= (b); --i) #define pi pair<int,int> #define ple tuple<int,int,int> #define fi first #define se second #define ii make_pair #define isz(a) ((int)a.size()) #define ALL(a) a.begin(), a.end() #define heap_max(a) priority_queue<a> #define heap_max(a) priority_queue<a,vector<a>,greater<a>> using namespace std; //#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 int N = 1e6 + 10; int n, q, l, r; string s[N]; struct Trie { struct Node { Node* child[30]; int cnt; vector<int>mem; Node () { for (int i = 0; i <= 26; ++i) child[i] = nullptr; cnt = 0; mem = {}; }; }; Node* root = new Node(); void add (string s, int idx) { Node* p = root; for (int i = 0; i < isz(s); ++i) { int c = (s[i] - 'A'); if (p -> child[c] == nullptr) { p -> child[c] = new Node(); } p = p -> child[c]; p -> mem.push_back(idx); } } void get_prefix (string s) { Node* p = root; for (int i = 0; i < isz(s); ++i) { int c = (s[i] - 'A'); if (p -> child[c] == nullptr) { return; } p = p -> child[c]; } l = p -> mem.front(); r = p -> mem.back(); return; } int get_sufix (string s) { Node* p = root; for (int i = 0; i < isz(s); ++i) { int c = (s[i] - 'A'); if (p -> child[c] == nullptr) { return 0; } p = p -> child[c]; } int left = lower_bound(ALL(p->mem), l)-p->mem.begin(); int right = upper_bound(ALL(p->mem), r)-p->mem.begin()-1; return right - left + 1; } } tree1, tree2; int main () { file("dynamic"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; FOR(i,1,n) cin >> s[i]; sort(s + 1, s + n + 1); for (int i = 1; i <= n; ++i) tree1.add(s[i], i); for (int i = 1; i <= n; ++i) { string rev = s[i]; reverse(ALL(rev)); tree2.add(rev, i); } while(q--) { string x, y; cin >> x >> y; l = -1; r = -1; tree1.get_prefix(x); if (l == -1) { cout << 0 << '\n'; continue; } cout << tree2.get_sufix(y) << '\n'; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 31836 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 385 ms | 666028 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 33488 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 31836 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |