제출 #320735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320735		parsabahrami	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	266 ms	209540 KiB

selling_rna

//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
    	if (b & 1) ans = ans * a % md;
    return ans;
}
const ll MAXN = 3e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll nxt[2][MAXN][30], L[MAXN], R[MAXN], n, q, id[2] = {1, 1};
vector<ll> vec[MAXN]; string C[MAXN];

void update1(string x, ll p) {
	ll v = 0;
	for (ll i = 0; i < sz(x); i++) {
		if (nxt[0][v][x[i] - 'A'] == 0) nxt[0][v][x[i] - 'A'] = id[0]++;
		L[v] = min(L[v], p);
		R[v] = max(R[v], p);
		v = nxt[0][v][x[i] - 'A'];
	}
	L[v] = min(L[v], p);
	R[v] = max(R[v], p);
}

void update2(string x, ll p) {
	ll v = 0;
	for (ll i = sz(x) - 1; ~i; i--) {
		if (nxt[1][v][x[i] - 'A'] == 0) nxt[1][v][x[i] - 'A'] = id[1]++;
		vec[v].push_back(p);
		v = nxt[1][v][x[i] - 'A'];
	}
	vec[v].push_back(p);
}

pll get1(string x) {
	ll v = 0;
	for (ll i = 0; i < sz(x); i++) {
		if (nxt[0][v][x[i] - 'A'] == 0) return {-1, -1};
		v = nxt[0][v][x[i] - 'A'];
	}
	return {L[v], R[v]};
}

ll get2(string x, ll l, ll r) {
	if (r == -1 || l == -1) return 0;
	ll v = 0;
	for (ll i = sz(x) - 1; ~i; i--) {
		if (nxt[1][v][x[i] - 'A'] == 0) return 15;
		v = nxt[1][v][x[i] - 'A'];
	}
	return upper_bound(all(vec[v]), r) - lower_bound(all(vec[v]), l);
}

int main() {
	fill(L, L + MAXN, MOD);
	scanf("%lld%lld", &n, &q);
	for (ll i = 1; i <= n; i++) {
		cin >> C[i];
	}
	sort(C + 1, C + n + 1);
	for (ll i = 1; i <= n; i++) {
		update1(C[i], i);
		update2(C[i], i);
	}
	while (q--) {
		string s, t;
		cin >> s >> t;
		pll X = get1(s);
		printf("%lld\n", get2(t, X.F, X.S));
	}
    return 0;
}

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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

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