oj.uz

Submission #434351

# Submission time Handle Problem Language Result Execution time Memory
434351 2021-06-21T03:15:13 Z ommivorous Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 457 ms 189636 KB 
/*
thisiscaau's code
trying my best for a better future
*/
#include <bits/stdc++.h>

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

using namespace std;
#define ll int
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll,ll> ii;
ll const mod = 1e9 + 7, MAXN = 3e6 + 5;


ll encode (char c){
	if (c == 'A') return 0;
	if (c == 'C') return 1;
	if (c == 'G') return 2;
	if (c == 'U') return 3;
	return 69696;
}

struct node {
	ll child[4];
	vector<ll> idx;
} trie[MAXN];

void gen (ll id){
	memset(trie[id].child,-1,sizeof(trie[id].child));
}

ll triesize = 0;
void push(string s,ll id){
    ll p = 0;
    for (int i = 0 ; i < s.size() ; i++){
    	char c = s[i];
        if (trie[p].child[encode(c)] == -1){
            gen(++triesize);
            trie[p].child[encode(c)] = triesize;
        }
        p = trie[p].child[encode(c)];
        trie[p].idx.pb(id);
    }
}

ll query (string s,ll l,ll r){
	ll p = 0;
	for (int i = 0 ; i < s.size() ; i++){
		char c = s[i];
		p = trie[p].child[encode(c)];
	}
	return lower_bound(trie[p].idx.begin(),trie[p].idx.end(),r) - lower_bound(trie[p].idx.begin(),trie[p].idx.end(),l);
}


ll tc,n,m;
string a[100005],suf[100005];
void aurelion_sol(){
	// solution goes here
	cin >> n >> m;
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	sort(a + 1,a + n + 1);
	for (int i = 1 ; i <= n ; i++){
		suf[i] = a[i];
		reverse(suf[i].begin(),suf[i].end());
	}
	gen(0);
	for (int i = 1 ; i <= n ; i++){
		push(suf[i],i);
	}
	while (m--){
		string p,q; cin >> p >> q;
		reverse(q.begin(),q.end());
		ll lf,rt;
		lf = lower_bound(a + 1,a + n + 1,p) - a;
		p[p.size() - 1]++;
		rt = upper_bound(a + 1,a + n + 1,p) - a;
		cout << query(q,lf,rt) << endl;
	}
}

signed main() {
#ifdef thisiscaau
	fileopen("input", "output");
#endif
#ifndef thisiscaau
	// fileopen1("LAH");
#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	tc = 1;
	while (tc--) aurelion_sol();
}

Compilation message

selling_rna.cpp: In function 'void push(std::string, int)':
selling_rna.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0 ; i < s.size() ; i++){
      |                      ~~^~~~~~~~~~
selling_rna.cpp: In function 'int query(std::string, int, int)':
selling_rna.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0 ; i < s.size() ; i++){
      |                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 123972 KB Output is correct
2 Correct 72 ms 123856 KB Output is correct
3 Correct 72 ms 123972 KB Output is correct
4 Correct 71 ms 123972 KB Output is correct
5 Correct 76 ms 123972 KB Output is correct
6 Correct 73 ms 123972 KB Output is correct
7 Correct 72 ms 123972 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 189636 KB Output is correct
2 Correct 236 ms 186304 KB Output is correct
3 Correct 145 ms 139460 KB Output is correct
4 Correct 141 ms 138796 KB Output is correct
5 Correct 193 ms 164804 KB Output is correct
6 Correct 204 ms 165316 KB Output is correct
7 Correct 132 ms 135716 KB Output is correct
8 Correct 237 ms 156228 KB Output is correct
9 Correct 228 ms 152356 KB Output is correct
10 Correct 173 ms 151936 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 124968 KB Output is correct
2 Correct 149 ms 124612 KB Output is correct
3 Correct 168 ms 124652 KB Output is correct
4 Correct 153 ms 124612 KB Output is correct
5 Correct 155 ms 124752 KB Output is correct
6 Correct 176 ms 124612 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 123972 KB Output is correct
2 Correct 72 ms 123856 KB Output is correct
3 Correct 72 ms 123972 KB Output is correct
4 Correct 71 ms 123972 KB Output is correct
5 Correct 76 ms 123972 KB Output is correct
6 Correct 73 ms 123972 KB Output is correct
7 Correct 72 ms 123972 KB Output is correct
8 Correct 229 ms 189636 KB Output is correct
9 Correct 236 ms 186304 KB Output is correct
10 Correct 145 ms 139460 KB Output is correct
11 Correct 141 ms 138796 KB Output is correct
12 Correct 193 ms 164804 KB Output is correct
13 Correct 204 ms 165316 KB Output is correct
14 Correct 132 ms 135716 KB Output is correct
15 Correct 237 ms 156228 KB Output is correct
16 Correct 228 ms 152356 KB Output is correct
17 Correct 173 ms 151936 KB Output is correct
18 Correct 191 ms 124968 KB Output is correct
19 Correct 149 ms 124612 KB Output is correct
20 Correct 168 ms 124652 KB Output is correct
21 Correct 153 ms 124612 KB Output is correct
22 Correct 155 ms 124752 KB Output is correct
23 Correct 176 ms 124612 KB Output is correct
24 Correct 284 ms 178756 KB Output is correct
25 Correct 350 ms 178884 KB Output is correct
26 Correct 276 ms 178076 KB Output is correct
27 Correct 207 ms 138688 KB Output is correct
28 Correct 457 ms 144364 KB Output is correct
29 Correct 360 ms 129268 KB Output is correct