Submission #276510

#	Time	Username	Problem	Language	Result	Execution time	Memory
276510		spdskatr	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	323 ms	224096 KiB

selling_rna

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#define SZ (1<<21)
#define fi first
#define se second
using namespace std;
struct entry {
	int i, l, r, f, a;
};

int N, M, ppos[100005], spos[100005], ans[100005];
string S[100005], P[100005], Q[100005];
vector<int> sw[2000005];
vector<entry> qu;
char bruh[] = { 'A', 'C', 'G', 'U' };

struct Trie {
	int ch[2000005][4], cnt = 2, sz[2000005], ind[2000005], cnt2;
	vector<int> occ[2000005];
	void build(int s) {
		int cur = 1;
		for (char c : S[s]) {
			for (int i = 0; i < 4; i++) {
				if (c == bruh[i]) {
					if (ch[cur][i] == 0) {
						ch[cur][i] = cnt++;
					}
					cur = ch[cur][i];
				}
			}
		}
		occ[cur].push_back(s);
	}
	void dfs(int x, int *p) {
		ind[x] = cnt2++;
		sz[x] = 1;
		for (int v : occ[x]) p[v] = ind[x];
		for (int i = 0; i < 4; i++) {
			if (ch[x][i]) {
				dfs(ch[x][i], p);
				sz[x] += sz[ch[x][i]];
			}
		}
	}
	int query(const string &s) {
		int cur = 1;
		for (char c : s) {
			for (int i = 0; i < 4; i++) {
				if (c == bruh[i]) {
					if (ch[cur][i] == 0) {
						return 0;
					}
					cur = ch[cur][i];
				}
			}
		}
		return cur;
	}
} tp, ts;

struct Segtree {
	int st[1<<22];
	void seg_inc(int i) {
		for (st[i += SZ] += 1; i > 1; i >>= 1) st[i>>1] = st[i] + st[i^1];
	}
	int seg_sum(int l, int r) {
		int res = 0;
		for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
			if (l&1) res += st[l++];
			if (r&1) res += st[--r];
		}
		return res;
	}
} st1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
		tp.build(i);
		reverse(S[i].begin(), S[i].end());
		ts.build(i);
	}
	tp.dfs(1, ppos);
	ts.dfs(1, spos);
	for (int i = 0; i < N; i++) {
		//printf("Point at (%d, %d)\n", ppos[i], spos[i]);
		sw[ppos[i]].push_back(spos[i]);
	}
	for (int i = 0; i < M; i++) {
		cin >> P[i] >> Q[i];
		reverse(Q[i].begin(), Q[i].end());
		int pn = tp.query(P[i]);
		int sn = ts.query(Q[i]);
		int pl = tp.ind[pn];
		int pr = tp.ind[pn] + tp.sz[pn];
		int sl = ts.ind[sn];
		int sr = ts.ind[sn] + ts.sz[sn];
		//printf("Query %d: [%d, %d), [%d, %d)\n", i, pl, pr, sl, sr);
		qu.push_back({ pl-1, sl, sr, -1, i });
		qu.push_back({ pr-1, sl, sr, 1, i });
	}
	sort(qu.begin(), qu.end(), [](entry l, entry r) {
		return l.i < r.i;
	});
	int cur = 0;
	for (entry e : qu) {
		while (cur <= e.i) {
			for (int x : sw[cur]) {
				//printf("Incrementing %d, %d\n", cur, x);
				st1.seg_inc(x);
			}
			cur++;
		}
		ans[e.a] += e.f * st1.seg_sum(e.l, e.r);
	}
	for (int i = 0; i < M; i++) {
		cout << ans[i] << "\n";
	}
}

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