제출 #376998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376998		peijar	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1004 ms	421012 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

struct Trie
{
	struct Node
	{
		array<int, 4> nxt;
		int tin=-1, tout=-1;
		Node()
		{
			fill(nxt.begin(), nxt.end(), -1);
		}
	};

	vector<Node> nodes;
	int time=0;

	Trie()
	{
		nodes.emplace_back();
	}

	int addWord(const vector<int> &word)
	{
		int curPos = 0;
		for (auto car : word)
		{
			if (nodes[curPos].nxt[car] == -1)
			{
				nodes[curPos].nxt[car] = nodes.size();
				nodes.emplace_back();
			}
			curPos = nodes[curPos].nxt[car];
		}
		return curPos;
	}

	void dfs(int iNoeud)
	{
		nodes[iNoeud].tin = time++;
		for (auto iProchain : nodes[iNoeud].nxt)
			if (iProchain != -1)
				dfs(iProchain);
		nodes[iNoeud].tout= time++;
	}

	void init()
	{
		dfs(0);
	}

	int traverse(const vector<int> &word)
	{
		int curPos = 0;
		for (auto car : word)
		{
			if (nodes[curPos].nxt[car] == -1)
				return -1;
			curPos = nodes[curPos].nxt[car];
		}
		return curPos;
	}
};

struct Fenwick
{
	vector<int> arr;
	int N;

	Fenwick(int nbElem)
	{
		arr.resize(nbElem+1);
		N = nbElem+1;
	}

	void update(int pos, int delta)
	{
		for (pos++; pos < N; pos += pos&-pos)
			arr[pos] += delta;
	}

	int sum(int r) // sum < r
	{
		int ret(0);
		for (; r; r -= r&-r)
			ret += arr[r];
		return ret;
	}

	int sum(int l, int r) // sum[l, r[
	{
		return sum(r) - sum(l);
	}
};

struct Fenwick2d
{
	vector<Fenwick> fen;
	int lim;
	vector<vector<int>> ys;
	Fenwick2d(int LIM) : lim(LIM+1), ys(lim) {}

	void fakeUpdate(int x, int y)
	{
		for (++x, ++y; x < lim; x += x&-x)
			ys[x].push_back(y);
	}

	void init()
	{
		for (int x(0); x < lim; ++x)
		{
			sort(ys[x].begin(), ys[x].end());
			ys[x].resize(unique(ys[x].begin(), ys[x].end())-ys[x].begin());
			fen.emplace_back(ys[x].size()+1);
		}
	}

	int getInd(int x, int y)
	{
		return lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin();
	}

	void update(int x, int y, int delta)
	{
		y++;
		for (x++; x < lim; x += x & -x)
			fen[x].update(getInd(x, y), delta);
	}

	int sum(int x, int y)
	{
		int ret=0;
		//cout << "query : " << x << ' ' << y << ' ';
		y++;
		for (; x; x -= x & -x)
			ret += fen[x].sum(getInd(x, y));
		//cout << ret << endl;
		return ret;
	}

	int sum(int lx, int rx, int ly, int ry)
	{
		return sum(rx+1, ry+1) - sum(lx, ry+1) - sum(rx+1, ly) + sum(lx, ly);
	}
};

const int MAX = 256;
int charDecode[MAX];

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	charDecode[(int)'A'] = 0;
	charDecode[(int)'C'] = 1;
	charDecode[(int)'G'] = 2;
	charDecode[(int)'U'] = 3;
	
	int nbChaines, nbRequetes;
	cin >> nbChaines >>nbRequetes;
	vector<vector<int>> chaines(nbChaines);
	vector<pair<int, int>> posTrie;

	Trie chainesEndroit, chainesEnvers;
	Fenwick2d fen((int)4e6+10);
	for (auto &v : chaines)
	{
		string s;
		cin >> s;
		for (auto c : s)
			v.push_back(charDecode[(int)c]);
		int a = chainesEndroit.addWord(v);
		reverse(v.begin(), v.end());
		int b = chainesEnvers.addWord(v);
		posTrie.emplace_back(a, b);
	}
	chainesEndroit.init(); chainesEnvers.init();
	vector<pair<vector<int>, vector<int>>> requetes(nbRequetes);
	for (auto [a, b] : posTrie)
		fen.fakeUpdate(chainesEndroit.nodes[a].tin, chainesEnvers.nodes[b].tin);
	fen.init();
	for (auto [a, b] : posTrie)
	{
		//cout << chainesEndroit.nodes[a].tin << ' ' <<  chainesEnvers.nodes[b].tin << endl;
		fen.update(chainesEndroit.nodes[a].tin, chainesEnvers.nodes[b].tin, 1);
	}

	for (auto &[p, q] : requetes)
	{
		string s, t;
		cin >> s >> t;
		for (auto v: s)
			p.push_back(charDecode[(int)v]);
		for (auto v : t)
			q.push_back(charDecode[(int)v]);
		reverse(q.begin(), q.end());
		int posEndroit = chainesEndroit.traverse(p);
		int posEnvers = chainesEnvers.traverse(q);
		if (posEndroit == -1 or posEnvers == -1)
			cout << 0 << '\n';
		else
		{
			int lx(chainesEndroit.nodes[posEndroit].tin);
			int rx(chainesEndroit.nodes[posEndroit].tout);
			int ly(chainesEnvers.nodes[posEnvers].tin);
			int ry(chainesEnvers.nodes[posEnvers].tout);
			int ret = fen.sum(lx, rx, ly, ry);
			//cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << ' ';
			cout << ret << '\n';
		}
	}
}

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