Submission #1042239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042239		milo_milkshake	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	135 ms	145464 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define uwu "RNA"

typedef long long ll;
#define pb push_back
#define endl '\n'
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
const int N = 1e5 + 3;
const int M = 2e6 + 2;
const int INF = 1e9 + 7;

int n, q;

string s[N];
int id[N];

int pre[M][4];
pair<int,int> range[M];
int nodepre = 1;

int suf[M][4];
vector <int> vt[M];
int nodesuf = 1;

int num(char c){
	if (c == 'U') return 3;
	if (c == 'G') return 1;
	return c - 'A';
}
void addpre(string s, int inc){
	int pos = 1, len = s.size();
	FOR(i, 0, len - 1){
		int c = num(s[i]); 
		if (!pre[pos][c]){
			pre[pos][c] = ++nodepre;
			range[nodepre].first = INF;
		}

		pos = pre[pos][c];  
		range[pos].first = min(range[pos].first, inc);
		range[pos].second = max(range[pos].second, inc);
	}
}
void addsuf(string s, int inc){
	int pos = 1, len = s.size();
	FORD(i, len - 1, 0){
		int c = num(s[i]);
		if (!suf[pos][c]) suf[pos][c] = ++nodesuf;
		pos = suf[pos][c]; vt[pos].pb(inc);
	}
}
pair<int,int> findpre(string s){
	int pos = 1, len = s.size();
	FOR(i, 0, len - 1){
		int c = num(s[i]); pos = pre[pos][c];  
		if (pos == 0) break;
	}
	return range[pos]; 
}
int calc(string s, pair<int,int> inc){
	int pos = 1, len = s.size();
	FORD(i, len - 1, 0){
		int c = num(s[i]); pos = suf[pos][c];
		if (pos == 0) break; 
	}

	int L = lower_bound(vt[pos].begin(), vt[pos].end(), inc.first) - vt[pos].begin();
	int R = upper_bound(vt[pos].begin(), vt[pos].end(), inc.second) - vt[pos].begin();
	return R - L;
}
void solve(void){
	FOR(i, 1, n) id[i] = i;
	sort(id + 1, id + n + 1, [&] (int u, int v){
		return s[u] < s[v];
	});

	FOR(i, 1, n){
		addpre(s[id[i]], i);
		addsuf(s[id[i]], i);
	}

	while(q--){
		string P, S; cin >> P >> S;
		cout << calc(S, findpre(P)) << endl;
	}
}
signed main(){
 	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if(fopen(uwu".inp","r")){
		freopen(uwu".inp","r",stdin);
		freopen(uwu".out","w",stdout);
	}

	cin >> n >> q;
	FOR(i, 1, n) cin >> s[i];

	solve();

	cerr << "\nTime used: " << clock() << "ms\n";
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen(uwu".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   freopen(uwu".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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