oj.uz

Submission #441070

# Submission time Handle Problem Language Result Execution time Memory
441070 2021-07-04T05:31:10 Z codebuster_10 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1372 ms 783544 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x;}
template<class H, class... T> void rd(H& h, T&... t) { rd(h); rd(t...);}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a);}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0;}

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}


void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  // remove this when size of input is not fixed.
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}


/*********************************************Look Below******************************************************************/










































template<const int ALPHABET>
struct prefix_tree {
	
	struct trie_node {
  	int link[ALPHABET];
    vector<int> who;
 
    trie_node() {
      memset(link, -1, sizeof(link));
    }
	};
	
	vector<trie_node> trie;
	
	prefix_tree(){
		trie.emplace_back();
	}
	
	void create_node(int parent, int c) {
    trie.emplace_back();
	}
	
	int get_or_create_node(int current, int c) {
    if (trie[current].link[c] < 0) {
      trie[current].link[c] = trie.size();
      create_node(current, c);
    }
 
    return trie[current].link[c];
	}
 
	int insert_str(const string & str,const int & i) {
		int current = 0;
    for(char c : str){
      current = get_or_create_node(current, c - 'A');
      trie[current].who.push_back(i);
 		}
    return current;
	}
	
	ar<int,2> query(const string & str){
		int current = 0;
		for(char c : str){
			if(trie[current].link[c-'A'] < 0) return ar<int,2>{-1,-1};
			current = trie[current].link[c-'A'];
		}
		return ar<int,2>{trie[current].who.front(),trie[current].who.back()};
	}
	
	int query(const string & str,int L,int R){
		int current = 0;
		for(char c : str){
			if(trie[current].link[c-'A'] < 0) return int(0);
			current = trie[current].link[c-'A'];
		}
		return int(upper_bound(all(trie[current].who),R) - lower_bound(all(trie[current].who),L));
	}
};

prefix_tree<26> trie, reverse_trie;

signed main(){
  setIO();
	int n,q; 
	rd(n,q);
	vt<string> s(n);
	rd(s);
	sort(all(s));
	
	f(i,0,n){
		trie.insert_str(s[i],i);
		reverse(all(s[i]));
		reverse_trie.insert_str(s[i],i);
	}
	
	while(q--){
		string p,q;
		rd(p,q);
		auto [L,R] = trie.query(p);
		reverse(all(q));
		cout << reverse_trie.query(q,L,R) << endl;
	}
	
}

Compilation message

selling_rna.cpp: In function 'void setIO(std::string)':
selling_rna.cpp:82:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 404 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 312 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 537340 KB Output is correct
2 Correct 756 ms 526732 KB Output is correct
3 Correct 729 ms 528824 KB Output is correct
4 Correct 727 ms 527028 KB Output is correct
5 Correct 1372 ms 783544 KB Output is correct
6 Correct 1163 ms 783472 KB Output is correct
7 Correct 94 ms 39660 KB Output is correct
8 Correct 762 ms 458412 KB Output is correct
9 Correct 664 ms 445732 KB Output is correct
10 Correct 608 ms 421500 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4564 KB Output is correct
2 Correct 26 ms 5388 KB Output is correct
3 Correct 31 ms 4736 KB Output is correct
4 Correct 21 ms 3780 KB Output is correct
5 Correct 27 ms 4920 KB Output is correct
6 Correct 33 ms 5088 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 404 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1024 ms 537340 KB Output is correct
9 Correct 756 ms 526732 KB Output is correct
10 Correct 729 ms 528824 KB Output is correct
11 Correct 727 ms 527028 KB Output is correct
12 Correct 1372 ms 783544 KB Output is correct
13 Correct 1163 ms 783472 KB Output is correct
14 Correct 94 ms 39660 KB Output is correct
15 Correct 762 ms 458412 KB Output is correct
16 Correct 664 ms 445732 KB Output is correct
17 Correct 608 ms 421500 KB Output is correct
18 Correct 30 ms 4564 KB Output is correct
19 Correct 26 ms 5388 KB Output is correct
20 Correct 31 ms 4736 KB Output is correct
21 Correct 21 ms 3780 KB Output is correct
22 Correct 27 ms 4920 KB Output is correct
23 Correct 33 ms 5088 KB Output is correct
24 Correct 727 ms 528600 KB Output is correct
25 Correct 725 ms 528612 KB Output is correct
26 Correct 713 ms 528584 KB Output is correct
27 Correct 693 ms 529448 KB Output is correct
28 Correct 302 ms 101164 KB Output is correct
29 Correct 105 ms 25664 KB Output is correct