Submission #1319737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319737		blackscreen1	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	227 ms	194724 KiB

selling_rna

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, q;
unordered_map<char, ll> mp;
string s, s2;
ll pre[2][100005];
pll a[100005];
pair<pll, pll> qu[400005];
ll ans[100005];
bool ir;
ll cp;
struct node {
	ll sz, rid;
	vector<ll> is;
	node *v[4];
	node () {
		sz = 0;
		rid = -1;
		iloop(0, 4) v[i] = nullptr;
	}
	void add(ll ci, ll cid) {
		sz++;
		if (ci == (ll)s.length()) {is.push_back(cid); return;}
		if (v[mp[s[ci]]] == nullptr) v[mp[s[ci]]] = new node();
		v[mp[s[ci]]]->add(ci+1, cid);
	}
	void dfs() {
		rid = cp;
		for (auto it : is) {pre[ir][it] = cp; cp++;}
		iloop(0, 4) if (v[i] != nullptr) v[i]->dfs();
	}
	pll find(ll ci) {
		if (ci == (ll)s.length()) return {rid, rid + sz - 1};
		if (v[mp[s[ci]]] == nullptr) return {0, -1};
		return v[mp[s[ci]]]->find(ci + 1);
	}
} *root, *rroot;
ll fenw[100005];
void upd(ll X, ll V) {
	X++;
	for (; X <= n; X += (X&(-X))) fenw[X] += V;
}
ll query(ll X) {
	X++;
	ll cans = 0;
	for (; X; X -= (X&(-X))) cans += fenw[X];
	return cans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
	cin >> n >> q;
	root = new node();
	rroot = new node();
	iloop(0, n) {
		cin >> s;
		root->add(0, i);
		reverse(s.begin(), s.end());
		rroot->add(0, i);
	}
	cp = 0, ir = 0;
	root->dfs();
	cp = 0, ir = 1;
	rroot->dfs();
	iloop(0, n) {
		a[i] = {pre[0][i], pre[1][i]};
		//cout << pre[0][i] << " " << pre[1][i] << "\n";
	}
	sort(a, a + n);
	iloop(0, q) {
		cin >> s >> s2;
		reverse(s2.begin(), s2.end());
		pair<pll, pll> tq = {root->find(0), {0, 0}};
		swap(s, s2);
		tq.second = rroot->find(0);
		//cout << tq.first.first << "," << tq.first.second << "," << tq.second.first << "," << tq.second.second << endl;
		qu[4*i] = {{tq.first.second, tq.second.second}, {1, i}};
		qu[4*i + 1] = {{tq.first.first - 1, tq.second.second}, {-1, i}};
		qu[4*i + 2] = {{tq.first.second, tq.second.first - 1}, {-1, i}};
		qu[4*i + 3] = {{tq.first.first - 1, tq.second.first - 1}, {1, i}};
	}
	sort(qu, qu + 4*q);
	ll cid = 0;
	iloop(0, 4*q) {
		//cout << qu[i].first.first << "," << qu[i].first.second << ":" << qu[i].second.first << "," << qu[i].second.second << endl;
		while (cid <= qu[i].first.first) {upd(a[cid].second, 1); cid++;}
		ans[qu[i].second.second] += qu[i].second.first * query(qu[i].first.second);
	}
	iloop(0, q) cout << ans[i] << "\n";
}

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