제출 #434351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434351		ommivorous	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	457 ms	189636 KiB

selling_rna

/*
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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40