제출 #647550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647550		ghostwriter	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1587 ms	179596 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
const pi M = {1e9 + 7, 1e9 + 9};
const pi base = {37, 127};
#define getid(x) (x == 'A'? 1 : x == 'G'? 2 : x == 'C'? 3 : 4)
struct Rna {
	str s;
	vpi h;
	Rna() {}
	void calh() {
		h.resize(sz(s));
		pi cur = {0, 0};
		FRN(i, sz(s)) {
			cur.st = (1LL * cur.st * base.st % M.st + getid(s[i])) % M.st;
			cur.nd = (1LL * cur.nd * base.nd % M.nd + getid(s[i])) % M.nd;
			h[i] = cur;
		}
	}
};
struct Query {
	str p, q;
	pi hq;
	vpi hp;
	Query() {}
	void calh() {
		hp.resize(sz(p));
		pi cur = {0, 0};
		FRN(i, sz(p)) {
			cur.st = (1LL * cur.st * base.st % M.st + getid(p[i])) % M.st;
			cur.nd = (1LL * cur.nd * base.nd % M.nd + getid(p[i])) % M.nd;
			hp[i] = cur;
		}
		hq = {0, 0};
		FRN(i, sz(q)) {
			hq.st = (1LL * hq.st * base.st % M.st + getid(q[i])) % M.st;
			hq.nd = (1LL * hq.nd * base.nd % M.nd + getid(q[i])) % M.nd;
		}
	}
};
const int N = 1e5 + 1;
const int TLEN = 2e6 + 1;
int n, m;
Rna a[N];
Query q[N];
pi P[N];
vpi v;
vi spos[TLEN];
int getpos(pi &x) { if (x > v.bk()) return -1; int ans = lb(all(v), x) - v.bg(); if (v[ans] != x) return -1; return ans; }
int get(vi &a, int l, int r) {
	if (l > a.bk()) return 0;
	l = lb(all(a), l) - a.bg();
	if (r >= a.bk()) r = sz(a) - 1;
	else r = ub(all(a), r) - a.bg() - 1;
	return r - l + 1;
}
pi geth(vpi &h, int l, int r) {
	pi ans;
	ans.st = (h[r].st - 1LL * (l? h[l - 1].st : 0) * P[r - l + 1].st % M.st + M.st) % M.st;
	ans.nd = (h[r].nd - 1LL * (l? h[l - 1].nd : 0) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
	return ans;
}
int mmatch(vpi &h, vpi &h1) {
	int l = 0, r = min(sz(h), sz(h1)) - 1, ans = -1;
	WHILE(l <= r) {
		int mid = l + (r - l) / 2;
		pi f = geth(h, 0, mid), s = geth(h1, 0, mid);
		if (f == s) {
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return ans + 1;
}
bool cmp(Rna &a, Rna &b) {
	int len = mmatch(a.h, b.h);
	if (len == sz(a.s) && len == sz(b.s)) return 0;
	if (len == sz(a.s)) return 1;
	if (len == sz(b.s)) return 0;
	return a.s[len] < b.s[len];
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    P[0] = {1, 1};
    FOR(i, 1, N - 1) {
    	P[i].st = 1LL * P[i - 1].st * base.st % M.st;
    	P[i].nd = 1LL * P[i - 1].nd * base.nd % M.nd;
    }
    cin >> n >> m;
    FOR(i, 1, n) {
    	cin >> a[i].s;
    	a[i].calh();
    	pi cur = {0, 0};
    	FSN(j, sz(a[i].s)) {
    		cur.st = (1LL * cur.st * base.st % M.st + getid(a[i].s[j])) % M.st;
    		cur.nd = (1LL * cur.nd * base.nd % M.nd + getid(a[i].s[j])) % M.nd;
    		v.pb(cur);
    	}
    }
    FOR(i, 1, m) {
    	cin >> q[i].p >> q[i].q;
    	reverse(all(q[i].q));
    	q[i].calh();
    }
    sort(a + 1, a + 1 + n, cmp);
    sort(all(v));
   	FOR(i, 1, n) {
    	pi cur = {0, 0};
    	FSN(j, sz(a[i].s)) {
    		cur.st = (1LL * cur.st * base.st % M.st + getid(a[i].s[j])) % M.st;
    		cur.nd = (1LL * cur.nd * base.nd % M.nd + getid(a[i].s[j])) % M.nd;
    		spos[getpos(cur)].pb(i);
    	}
    }
    // FOR(i, 1, n) {
    // 	cerr << i << " : " << a[i].s << '\n';
    // }
    FOR(i, 1, m) {
    	Query &curq = q[i];
    	int pos = getpos(curq.hq);
    	if (pos == -1) {
    		cout << 0 << '\n';
    		continue;
    	}
    	int clen = sz(curq.p), l = 1, r = n, lans = -1, uans = -1;
    	WHILE(l <= r) {
    		int mid = l + (r - l) / 2;
    		int len = mmatch(a[mid].h, curq.hp);
    		if (len == clen) {
    			lans = mid;
    			r = mid - 1;
    		}
    		else if (a[mid].s[len] < curq.p[len]) l = mid + 1;
    		else r = mid - 1;
    	}
    	if (lans == -1) {
    		cout << 0 << '\n';
    		continue;
    	}
    	l = 1; r = n;
    	WHILE(l <= r) {
    		int mid = l + (r - l) / 2;
    		int len = mmatch(a[mid].h, curq.hp);
    		if (len == clen) {
    			uans = mid;
    			l = mid + 1;
    		}
    		else if (a[mid].s[len] < curq.p[len]) l = mid + 1;
    		else r = mid - 1;
    	}
    	cout << get(spos[pos], lans, uans) << '\n';
    }
    return 0;
}
/*
2 3
AUGC
AGC
G C
AU C
A C
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

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

selling_rna.cpp: In member function 'void Rna::calh()':
selling_rna.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
selling_rna.cpp:61:3: note: in expansion of macro 'FRN'
   61 |   FRN(i, sz(s)) {
      |   ^~~
selling_rna.cpp: In member function 'void Query::calh()':
selling_rna.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
selling_rna.cpp:76:3: note: in expansion of macro 'FRN'
   76 |   FRN(i, sz(p)) {
      |   ^~~
selling_rna.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
selling_rna.cpp:82:3: note: in expansion of macro 'FRN'
   82 |   FRN(i, sz(q)) {
      |   ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
selling_rna.cpp:135:5: note: in expansion of macro 'FOR'
  135 |     FOR(i, 1, N - 1) {
      |     ^~~
selling_rna.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
selling_rna.cpp:140:5: note: in expansion of macro 'FOR'
  140 |     FOR(i, 1, n) {
      |     ^~~
selling_rna.cpp:35:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
      |                            ^
selling_rna.cpp:144:6: note: in expansion of macro 'FSN'
  144 |      FSN(j, sz(a[i].s)) {
      |      ^~~
selling_rna.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
selling_rna.cpp:150:5: note: in expansion of macro 'FOR'
  150 |     FOR(i, 1, m) {
      |     ^~~
selling_rna.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
selling_rna.cpp:157:5: note: in expansion of macro 'FOR'
  157 |     FOR(i, 1, n) {
      |     ^~~
selling_rna.cpp:35:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
      |                            ^
selling_rna.cpp:159:6: note: in expansion of macro 'FSN'
  159 |      FSN(j, sz(a[i].s)) {
      |      ^~~
selling_rna.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
selling_rna.cpp:168:5: note: in expansion of macro 'FOR'
  168 |     FOR(i, 1, m) {
      |     ^~~

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