oj.uz

Submission #376998

# Submission time Handle Problem Language Result Execution time Memory
376998 2021-03-12T16:42:09 Z peijar Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1004 ms 421012 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 344904 KB Output is correct
2 Correct 457 ms 344828 KB Output is correct
3 Correct 457 ms 345092 KB Output is correct
4 Correct 460 ms 344920 KB Output is correct
5 Correct 462 ms 344840 KB Output is correct
6 Correct 459 ms 344776 KB Output is correct
7 Correct 456 ms 344904 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 417380 KB Output is correct
2 Correct 660 ms 416820 KB Output is correct
3 Correct 658 ms 418156 KB Output is correct
4 Correct 661 ms 416364 KB Output is correct
5 Correct 718 ms 420020 KB Output is correct
6 Correct 715 ms 421012 KB Output is correct
7 Correct 576 ms 382024 KB Output is correct
8 Correct 682 ms 416112 KB Output is correct
9 Correct 667 ms 410696 KB Output is correct
10 Correct 629 ms 395512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 358928 KB Output is correct
2 Correct 541 ms 353512 KB Output is correct
3 Correct 603 ms 356168 KB Output is correct
4 Correct 519 ms 354812 KB Output is correct
5 Correct 581 ms 353352 KB Output is correct
6 Correct 621 ms 356060 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 344904 KB Output is correct
2 Correct 457 ms 344828 KB Output is correct
3 Correct 457 ms 345092 KB Output is correct
4 Correct 460 ms 344920 KB Output is correct
5 Correct 462 ms 344840 KB Output is correct
6 Correct 459 ms 344776 KB Output is correct
7 Correct 456 ms 344904 KB Output is correct
8 Correct 644 ms 417380 KB Output is correct
9 Correct 660 ms 416820 KB Output is correct
10 Correct 658 ms 418156 KB Output is correct
11 Correct 661 ms 416364 KB Output is correct
12 Correct 718 ms 420020 KB Output is correct
13 Correct 715 ms 421012 KB Output is correct
14 Correct 576 ms 382024 KB Output is correct
15 Correct 682 ms 416112 KB Output is correct
16 Correct 667 ms 410696 KB Output is correct
17 Correct 629 ms 395512 KB Output is correct
18 Correct 538 ms 358928 KB Output is correct
19 Correct 541 ms 353512 KB Output is correct
20 Correct 603 ms 356168 KB Output is correct
21 Correct 519 ms 354812 KB Output is correct
22 Correct 581 ms 353352 KB Output is correct
23 Correct 621 ms 356060 KB Output is correct
24 Correct 700 ms 412756 KB Output is correct
25 Correct 750 ms 416072 KB Output is correct
26 Correct 673 ms 411476 KB Output is correct
27 Correct 708 ms 412380 KB Output is correct
28 Correct 1004 ms 399208 KB Output is correct
29 Correct 736 ms 388616 KB Output is correct