oj.uz

Submission #785087

# Submission time Handle Problem Language Result Execution time Memory
785087 2023-07-17T04:49:22 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 788 ms 822992 KB 
//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";
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 562112 KB Output is correct
2 Correct 546 ms 562068 KB Output is correct
3 Correct 439 ms 541256 KB Output is correct
4 Correct 415 ms 541372 KB Output is correct
5 Correct 788 ms 822992 KB Output is correct
6 Correct 761 ms 822892 KB Output is correct
7 Correct 48 ms 18656 KB Output is correct
8 Correct 510 ms 468500 KB Output is correct
9 Correct 437 ms 450640 KB Output is correct
10 Correct 382 ms 427768 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3152 KB Output is correct
2 Correct 18 ms 4464 KB Output is correct
3 Correct 19 ms 3656 KB Output is correct
4 Correct 14 ms 2464 KB Output is correct
5 Correct 19 ms 3836 KB Output is correct
6 Correct 25 ms 3880 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 533 ms 562112 KB Output is correct
9 Correct 546 ms 562068 KB Output is correct
10 Correct 439 ms 541256 KB Output is correct
11 Correct 415 ms 541372 KB Output is correct
12 Correct 788 ms 822992 KB Output is correct
13 Correct 761 ms 822892 KB Output is correct
14 Correct 48 ms 18656 KB Output is correct
15 Correct 510 ms 468500 KB Output is correct
16 Correct 437 ms 450640 KB Output is correct
17 Correct 382 ms 427768 KB Output is correct
18 Correct 19 ms 3152 KB Output is correct
19 Correct 18 ms 4464 KB Output is correct
20 Correct 19 ms 3656 KB Output is correct
21 Correct 14 ms 2464 KB Output is correct
22 Correct 19 ms 3836 KB Output is correct
23 Correct 25 ms 3880 KB Output is correct
24 Correct 501 ms 563388 KB Output is correct
25 Correct 487 ms 563248 KB Output is correct
26 Correct 473 ms 563236 KB Output is correct
27 Correct 426 ms 543420 KB Output is correct
28 Correct 173 ms 87308 KB Output is correct
29 Correct 57 ms 13304 KB Output is correct