제출 #531486

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

selling_rna

#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?)
*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40