oj.uz

Submission #434209

# Submission time Handle Problem Language Result Execution time Memory
434209 2021-06-20T18:19:49 Z dutch Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 227 ms 116324 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 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 320 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 180 ms 116324 KB Output is correct
2 Correct 150 ms 110764 KB Output is correct
3 Correct 35 ms 9376 KB Output is correct
4 Correct 34 ms 9408 KB Output is correct
5 Correct 109 ms 72744 KB Output is correct
6 Correct 112 ms 73688 KB Output is correct
7 Correct 41 ms 12016 KB Output is correct
8 Correct 105 ms 51884 KB Output is correct
9 Correct 86 ms 46020 KB Output is correct
10 Correct 65 ms 39448 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 6884 KB Output is correct
2 Correct 45 ms 4428 KB Output is correct
3 Correct 59 ms 5688 KB Output is correct
4 Correct 48 ms 4712 KB Output is correct
5 Correct 45 ms 4316 KB Output is correct
6 Correct 59 ms 5536 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 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 320 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 180 ms 116324 KB Output is correct
9 Correct 150 ms 110764 KB Output is correct
10 Correct 35 ms 9376 KB Output is correct
11 Correct 34 ms 9408 KB Output is correct
12 Correct 109 ms 72744 KB Output is correct
13 Correct 112 ms 73688 KB Output is correct
14 Correct 41 ms 12016 KB Output is correct
15 Correct 105 ms 51884 KB Output is correct
16 Correct 86 ms 46020 KB Output is correct
17 Correct 65 ms 39448 KB Output is correct
18 Correct 75 ms 6884 KB Output is correct
19 Correct 45 ms 4428 KB Output is correct
20 Correct 59 ms 5688 KB Output is correct
21 Correct 48 ms 4712 KB Output is correct
22 Correct 45 ms 4316 KB Output is correct
23 Correct 59 ms 5536 KB Output is correct
24 Correct 156 ms 98320 KB Output is correct
25 Correct 193 ms 101168 KB Output is correct
26 Correct 140 ms 96324 KB Output is correct
27 Correct 60 ms 11148 KB Output is correct
28 Correct 227 ms 33344 KB Output is correct
29 Correct 173 ms 15784 KB Output is correct