Submission #242882

#	Time	Username	Problem	Language	Result	Execution time	Memory
242882		Atalasion	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	640 ms	40472 KiB

selling_rna

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define SZ(x) (int)x.size()
//5:20

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, m, ans[N], a[N], b[N], koj[N], fen[N];
string S[N], R[N];
pair<string, int> suf[N], pre[N];
vector<pii> QQ[N];

int LCP(int id, string s){
	for(int i = 0; i < min(SZ(s), SZ(S[id])); i++){
		if (s[i] != S[id][i]) return i;
	}
	return min(SZ(s), SZ(S[id]));
}

bool com(int id, string s){
	for (int i = 0; i < min(SZ(s), SZ(S[id])); i++){
		if (S[id][i] < s[i]) return 1;
		if (S[id][i] > s[i]) return 0;
	}
	return (SZ(S[id]) < SZ(s));
}

int LCP2(int id, string s){
	for(int i = 0; i < min(SZ(s), SZ(R[id])); i++){
		if (s[i] != R[id][i]) return i;
	}
	return min(SZ(s), SZ(R[id]));
}


bool com2(int id, string s){
	for (int i = 0; i < min(SZ(s), SZ(R[id])); i++){
		if (R[id][i] < s[i]) return 1;
		if (R[id][i] > s[i]) return 0;
	}
	return (SZ(R[id]) < SZ(s));
}

vector<pair<pair<pii, pii>, int>> Q;

inline void add(int id, int x){
	for (; id < N; id += id & (-id)) fen[id] += x;
	return;
}

int get(int id){
	int res = 0;
	for (; id > 0; id -= id & (-id)) res += fen[id];
	return res;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> S[i];
		R[i] = S[i];
		pre[i] = {S[i], i};
		reverse(all(R[i]));
		suf[i] = {R[i], i};
	}
	sort(suf + 1, suf + n + 1);
	sort(pre + 1, pre + n + 1);
	for (int tmp = 1; tmp <= m; tmp++){
		string s, p;
		cin >> s >> p;
//		cout << "YES" << endl;
		reverse(all(p));
		int l = 0, r = n + 1;
		while (r - l > 1){
//			cout << l << ' ' << r << endl;
			int md = (l + r) >> 1;
			if (com(pre[md].S, s)) l = md;
			else r = md;
		}
		l++;
		if (LCP(pre[l].S, s) != s.size()) continue;
		int L = l, R = n + 1;
//		cout << "YES" << endl;
		while (R - L > 1){
			int md = (L + R) >> 1;
			if (LCP(pre[md].S, s) == s.size()) L = md;
			else R = md;
		}
		r = L;
		int ll = l, rr = r;
		l = 0, r = n + 1;
		while (r - l > 1){
			int md = (l + r) >> 1;
			if (com2(suf[md].S, p)) l = md;
			else r = md; 
		}
		l++;
		if (LCP2(suf[l].S, p) != p.size()) continue;
		L = l, R = n + 1;
		while (R - L > 1){
			int md = (L + R) >> 1;
			if (LCP2(suf[md].S, p) == p.size()) L = md;
			else R = md;
		}
		r = L;
		Q.pb({{{ll, rr}, {l, r}}, tmp});
//		cout << tmp << ' ' << ll << ' ' << rr << ' ' << l << ' ' << r << '\n';
	}
	for (int i = 1; i <= n; i++){
		a[i] = pre[i].S;
	}
	for (int i = 1; i <= n; i++){
		b[i] = suf[i].S;
		koj[b[i]] = i;
	}
	for (auto u:Q){
		QQ[u.F.F.S].pb({u.F.S.S, u.S});
		QQ[u.F.F.S].pb({u.F.S.F - 1, -u.S});
		QQ[u.F.F.F - 1].pb({u.F.S.F - 1, u.S});
		QQ[u.F.F.F - 1].pb({u.F.S.S, -u.S});
	}
	for (int i = 1; i <= n; i++){
		add(koj[a[i]], 1);
		for (auto u:QQ[i]){
			int x = get(u.F);
//			cout << i << ' ' << u.F << ' ' << u.S << ' ' << x << '\n';	
			if (u.S < 0) ans[-u.S] -= x;
			else ans[u.S] += x;
		}
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (LCP(pre[l].S, s) != s.size()) continue;
       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:102:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (LCP(pre[md].S, s) == s.size()) L = md;
        ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:114:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (LCP2(suf[l].S, p) != p.size()) continue;
       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:118:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (LCP2(suf[md].S, p) == p.size()) L = md;
        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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