제출 #785087

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

selling_rna

//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
	#include "/home/trucmai/.vim/tools.h"
	#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
	#else
	#define debug(x...)
#endif

void open(){
  if(fopen("i.inp","r")){
    freopen("i.inp","r",stdin);
    freopen("o.out","w",stdout);
  }
}

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e5 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;

struct trie{
	struct node{
		array<ll,26>nxt; 
		ll l,r; bool ex;
		vector<ll>lst;
		node(){}
		node(ll l,ll r,bool ex):l(l),r(r),ex(ex){nxt.fill(-1);}
	};
	bool rev; 
	vector<node>tr{node(INF,-INF,false)};
	trie(bool rev):rev(rev){}
	void add(string &s,ll &idx){ 
		ll ptr = 0; 
		for(ll i = 0;i < s.size();++i){
			ll ch = s[i] - 'A'; 
			if(tr[ptr].nxt[ch] == -1){
				tr[ptr].nxt[ch] = tr.size(); 
				tr.push_back(node(INF,-INF,false));
			}
			ptr = tr[ptr].nxt[ch];
			if(!rev){
				tr[ptr].l = min(tr[ptr].l,idx);
				tr[ptr].r = max(tr[ptr].r,idx);
			}else tr[ptr].lst.push_back(idx);
		}
		tr[ptr].ex = true; 
	}
	pi get(string &s){
		ll ptr = 0;
		for(ll i  = 0;i < s.size();++i){ 
			ll ch = s[i] - 'A'; 
			if(tr[ptr].nxt[ch] == -1) return {-1,-1};
			ptr = tr[ptr].nxt[ch];
		}
		return {tr[ptr].l,tr[ptr].r};	
	}
	ll query(string &s,pi pos){
		reverse(all(s));
		ll ptr = 0; 
		for(ll i = 0;i < s.size();++i){
			ll ch = s[i] - 'A';
			if(tr[ptr].nxt[ch] == -1) return 0;
			ptr = tr[ptr].nxt[ch];
		}
		ll resl = lower_bound(all(tr[ptr].lst),pos.fi) - tr[ptr].lst.begin(),
			 resr = upper_bound(all(tr[ptr].lst),pos.se) - tr[ptr].lst.begin();
		return resr - resl;
	}
};

ll n,m;
trie t1(false),t2(true);
vector<string>s;
void solve(){
	cin>>n>>m;s.resize(n+1);
	for(ll i = 1;i <= n;++i) cin>>s[i];
	sort(s.begin()+1,s.end());
	for(ll i = 1;i <= n;++i){
		t1.add(s[i],i); 
		reverse(all(s[i]));
		t2.add(s[i],i);
	}
	for(ll i = 1;i <= m;++i){
		string p,q; cin>>p>>q;
		pi res = t1.get(p);
		//cout<<res.fi<<spc<<res.se<<endl;
		cout<<t2.query(q,res)<<endl;
	}
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  open();
  ll t = 1; //cin>>t;
  while(t--) solve(); 
  cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

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

selling_rna.cpp: In member function 'void trie::add(std::string&, long long int&)':
selling_rna.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(ll i = 0;i < s.size();++i){
      |                ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<long long int, long long int> trie::get(std::string&)':
selling_rna.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(ll i  = 0;i < s.size();++i){
      |                 ~~^~~~~~~~~~
selling_rna.cpp: In member function 'long long int trie::query(std::string&, std::pair<long long int, long long int>)':
selling_rna.cpp:73:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(ll i = 0;i < s.size();++i){
      |                ~~^~~~~~~~~~
selling_rna.cpp: In function 'void open()':
selling_rna.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40