oj.uz

Submission #531486

# Submission time Handle Problem Language Result Execution time Memory
531486 2022-02-28T21:03:34 Z fcw Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 244 ms 115104 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

int f(char c){
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	return 3;
}


struct trie_t{
	vector<array<int, 4>>nodes;
	vector<vector<int>>v;
	int n, m;
	vector<int>x, a, b;
	trie_t (int c = 0, int d = 0) : n(c), m(d), x(c), a(d), b(d), nodes(1, {-1, -1, -1, -1}), v(1) {}
	int timer = 0;
	void add(string s, int id){
		int cur = 0;
		for(char c : s){
			int e = f(c);
			if(nodes[cur][e] == -1){
				nodes[cur][e] = (int)nodes.size();
				nodes.push_back({-1, -1, -1, -1});
				v.push_back({});
			}
			cur = nodes[cur][e];
		}
		v[cur].push_back(id);
	}
	void dfs(int cur){
		for(int u : v[cur]){
			if(u < m) a[u] = timer;
			else x[u-m] = timer++;
		}
		for(int e=0;e<4;e++){
			if(nodes[cur][e] == -1) continue;
			dfs(nodes[cur][e]);
		}
		for(int u : v[cur]){
			if(u < m) b[u] = timer - 1;
		}
	}
};

template<typename T> struct FT {
	vector<T> s;
	FT(int n) : s(n) {}
	FT(const vector<T>& A) : s(int(A.size())) {
		const int N = int(A.size());
		for (int pos = 0; pos < N; ++pos) {
			s[pos] += A[pos];
			int nxt = (pos | (pos + 1));
			if (nxt < N) s[nxt] += s[pos];
		}
	}
	void update(int pos, T dif) { // a[pos] += dif
		for (; pos < (int)s.size(); pos |= pos + 1) s[pos] += dif;
	}
	T query(int pos) { // sum of values in [0, pos)
		T res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int lower_bound(T sum) {// min pos st sum of [0, pos] >= sum
		// Returns n if no sum is >= sum, or -1 if empty sum is.
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1 << 25; pw; pw >>= 1) {
			if (pos + pw <= (int)s.size() && s[pos + pw-1] < sum)
				pos += pw, sum -= s[pos-1];
		}
		return pos;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	trie_t trie(n, m), rtrie(n, m);
	vector<string>s(n), t(n), p(m), q(m);
	for(int i=0;i<n;i++){
		cin>>s[i];
		t[i] = s[i];
		reverse(t[i].begin(), t[i].end());
	}
	for(int i=0;i<m;i++){
		cin>>p[i]>>q[i];
		reverse(q[i].begin(), q[i].end());
	}
	for(int i=0;i<m;i++){
		trie.add(p[i], i);
		rtrie.add(q[i], i);
	}
	for(int i=0;i<n;i++){
		trie.add(s[i], m+i);
		rtrie.add(t[i], m+i);
	}
	trie.dfs(0);
	rtrie.dfs(0);
	vector<int>x = trie.x, a = trie.a, b = trie.b;
	vector<int>y = rtrie.x, c = rtrie.a, d = rtrie.b;
	vector<array<int, 4>>v;
	for(int i=0;i<m;i++){
	}
	for(int i=0;i<n;i++){
		v.push_back({y[i], -1, x[i], 0});
	}
	for(int i=0;i<m;i++){
		if(d[i] >= c[i] && b[i] >= a[i]){
			v.push_back({d[i], a[i], b[i], i+1});
			v.push_back({c[i] - 1, a[i], b[i], -i-1});
		}
	}
	FT<int>seg(n);
	sort(v.begin(), v.end());
	vector<int>ans(m);
	for(auto [_, j, k, id] : v){
		if(j == -1){
			seg.update(k, 1);
		}
		else{
			int res = seg.query(k+1) - seg.query(j);
			if(id > 0) ans[id-1] += res;
			else ans[-id-1] -= res;
		}
	}
	for(int i=0;i<m;i++) cout<<ans[i]<<"\n";

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Compilation message

selling_rna.cpp: In constructor 'trie_t::trie_t(int, int)':
selling_rna.cpp:28:19: warning: 'trie_t::b' will be initialized after [-Wreorder]
   28 |  vector<int>x, a, b;
      |                   ^
selling_rna.cpp:25:23: warning:   'std::vector<std::array<int, 4> > trie_t::nodes' [-Wreorder]
   25 |  vector<array<int, 4>>nodes;
      |                       ^~~~~
selling_rna.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  trie_t (int c = 0, int d = 0) : n(c), m(d), x(c), a(d), b(d), nodes(1, {-1, -1, -1, -1}), v(1) {}
      |  ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 88380 KB Output is correct
2 Correct 180 ms 85100 KB Output is correct
3 Correct 179 ms 87928 KB Output is correct
4 Correct 158 ms 84532 KB Output is correct
5 Correct 232 ms 114820 KB Output is correct
6 Correct 244 ms 115104 KB Output is correct
7 Correct 42 ms 14236 KB Output is correct
8 Correct 146 ms 71976 KB Output is correct
9 Correct 143 ms 69312 KB Output is correct
10 Correct 111 ms 64412 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14416 KB Output is correct
2 Correct 32 ms 8800 KB Output is correct
3 Correct 41 ms 11096 KB Output is correct
4 Correct 32 ms 9248 KB Output is correct
5 Correct 32 ms 8852 KB Output is correct
6 Correct 40 ms 11028 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 165 ms 88380 KB Output is correct
9 Correct 180 ms 85100 KB Output is correct
10 Correct 179 ms 87928 KB Output is correct
11 Correct 158 ms 84532 KB Output is correct
12 Correct 232 ms 114820 KB Output is correct
13 Correct 244 ms 115104 KB Output is correct
14 Correct 42 ms 14236 KB Output is correct
15 Correct 146 ms 71976 KB Output is correct
16 Correct 143 ms 69312 KB Output is correct
17 Correct 111 ms 64412 KB Output is correct
18 Correct 47 ms 14416 KB Output is correct
19 Correct 32 ms 8800 KB Output is correct
20 Correct 41 ms 11096 KB Output is correct
21 Correct 32 ms 9248 KB Output is correct
22 Correct 32 ms 8852 KB Output is correct
23 Correct 40 ms 11028 KB Output is correct
24 Correct 158 ms 79560 KB Output is correct
25 Correct 185 ms 84548 KB Output is correct
26 Correct 158 ms 78424 KB Output is correct
27 Correct 167 ms 79504 KB Output is correct
28 Correct 166 ms 52816 KB Output is correct
29 Correct 120 ms 31004 KB Output is correct