제출 #434209

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

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define num(c) (c > 'A') + (c > 'C') + (c > 'G') + (c > 'U')

template<class T> struct fenwick{
    vector<T> a; int n, p=1<<30; T s;
    fenwick(int N) : a(++(n=N)) {}
    fenwick& operator[](int i){ p = i; return *this; }
    void operator+=(T v){
        for(++p; p<n; p+=p&-p) a[p] += v; }
    void operator=(T v){ operator+=(v - operator()(p, p)); }
    T operator()(int i){
        for(s=0, ++i; i; i^=i&-i) s += a[i];
        return s; }
    T operator()(int l, int r){ return operator()(r) - operator()(l-1); }
    int lower_bound(T v){
        for(s=0, p=1<<21; p/=2; ) if(s+p<=n && a[s+p]<v) v -= a[s+=p];
        return s;
    }
};

const int LIM = (int)2e6+1;

array<int, 4> g[LIM];
int t0[LIM], t1[LIM], dfsTimer = -1;

void dfs(int u){
	t0[u] = ++dfsTimer;
	for(int &v : g[u]) if(v > 0) dfs(v);
	t1[u] = dfsTimer;
}

bool comp(const string &x, const string &y, bool eq){ // <=
	int a = x.size(), b = y.size();
	for(int i=0; i<b; ++i){
		if(i == a) return 1;
		if(x[i] < y[i]) return 1;
		if(x[i] > y[i]) return 0;
	}
	return eq;
}
bool comp1(const string &x, const string &y){ // >
	int a = x.size(), b = y.size();
	for(int i=0; i<b; ++i){
		if(i == a) return 0;
		if(x[i] < y[i]) return 0;
		if(x[i] > y[i]) return 1;
	}
	return 0;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	// cout << comp("U", "G", 1) sp "ok" nl;


	int n, m; cin >> n >> m;

	string a[n];
	int pos[n], ans[m];
	pair<array<string, 2>, int> b[m];
	for(auto &i : a) cin >> i;
	for(int i=0; i<m; ++i){
		cin >> b[i].first[0] >> b[i].first[1];
		b[i].second = i;
	}
	sort(a, a+n);
	sort(b, b+m);

	int curr = 1;
	for(int i=0; i<n; ++i){
		reverse(a[i].begin(), a[i].end());

		int u = 0;
		for(auto &c : a[i]){
			if(!g[u][num(c)]) g[u][num(c)] = curr++;
			u = g[u][num(c)];
		}
		pos[i] = u;

		reverse(a[i].begin(), a[i].end());
	}

	dfs(0);
	fenwick<int> f(++dfsTimer);
	int l = 0, r = 1;
	f[t0[pos[0]]] += 1;

	for(auto &i : b){
		while(r < n && comp(a[r], i.first[0], 1)){
			f[t0[pos[r]]] += +1;
			++r;
		}
		while(l < r && comp(a[l], i.first[0], 0)){
			f[t0[pos[l]]] += -1;
			++l;
		}
		while(l < r && comp1(a[r-1], i.first[0])){
			f[t0[pos[r-1]]] += -1;
			--r;
		}

		int u = 0;
		reverse(i.first[1].begin(), i.first[1].end());
		for(auto &c : i.first[1]){
			if(!g[u][num(c)]) g[u][num(c)] = curr++;
			u = g[u][num(c)];
			if(u < 0) break;
		}
		if(u >= 0) ans[i.second] = f(t0[u], t1[u]);
		else ans[i.second] = 0;
	}

	for(int i : ans) cout << i << '\n';
}

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