oj.uz

Submission #1090279

# Submission time Handle Problem Language Result Execution time Memory
1090279 2024-09-18T07:13:44 Z baoheyhey Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 189 ms 200776 KB 
#include<bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FOD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
#define ll long long 
#define ALL(a) a.begin(), a.end()
#define sz(a) a.size()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define el "\n"
#define bit(a, x) (a >> x & 1)
#define X first
#define Y second
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define uni(a) sort(ALL(a)), a.resize(unique(ALL(a)) - a.begin())
using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

const int maxn = 1e5 + 5;

string s[maxn];
int n, m;

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

struct Trie{
	struct Node{
		Node* child[4];
		int cnt, maxx, minn;
		Node(){
			FOR(i, 0, 3) child[i] = NULL;
			maxx = -1e9;
			minn = 1e9;
		}
	};
		
	Node *root;
	int cur;
	Trie() : cur(0){
		root = new Node();
	};

	void add(string s, int id){
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) p -> child[c] = new Node();
				p = p -> child[c];
				p -> maxx = max(p -> maxx, id);
				p -> minn = min(p -> minn, id);
		}
	}

	pii query(string s){
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) return {-1, -1};
			p = p -> child[c];
		}
		return {p -> minn, p -> maxx};
		}
} trie;

struct InTrie{
	struct Node{
		Node *child[4];
		vi list;
		Node (){
			FOR(i, 0, 3) child[i] = NULL;
			list.clear();
		}
	};
	Node* root;
	int cur;
	InTrie() : cur(0){
		root = new Node();
	};

	void add(string s, int id){
		reverse(ALL(s));
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) p -> child[c] = new Node();
			p = p -> child[c];
			p -> list.pb(id);
		}
	}

	int query(string s, pii range){
		reverse(ALL(s));
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) return 0;
			p = p -> child[c];
		}
		int l = lower_bound(ALL(p -> list), range.X) - p -> list.begin();
		int r = upper_bound(ALL(p -> list), range.Y) - p -> list.begin() - 1;
		return r - l + 1;
	}
} trie1;

signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> n >> m;
	FOR(i, 1, n) cin >> s[i];
	sort(s + 1, s + n + 1);
	FOR(i, 1, n){
		trie.add(s[i], i);
		trie1.add(s[i], i);
	}
	while(m--){
		string p, q;
		cin >> p >> q;
		pii range = trie.query(p);
		if(range.X == -1) cout << 0;
		else cout << trie1.query(q, range);
		cout << el;
	}
	cerr << "Time elapsed: " << TIME << " s" << el;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 194456 KB Output is correct
2 Correct 179 ms 184588 KB Output is correct
3 Correct 118 ms 142244 KB Output is correct
4 Correct 123 ms 135768 KB Output is correct
5 Correct 164 ms 197784 KB Output is correct
6 Correct 189 ms 200776 KB Output is correct
7 Correct 50 ms 19028 KB Output is correct
8 Correct 137 ms 129108 KB Output is correct
9 Correct 117 ms 110564 KB Output is correct
10 Correct 88 ms 105552 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4824 KB Output is correct
2 Correct 14 ms 4888 KB Output is correct
3 Correct 16 ms 4700 KB Output is correct
4 Correct 13 ms 4444 KB Output is correct
5 Correct 14 ms 4876 KB Output is correct
6 Correct 17 ms 4696 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 186 ms 194456 KB Output is correct
9 Correct 179 ms 184588 KB Output is correct
10 Correct 118 ms 142244 KB Output is correct
11 Correct 123 ms 135768 KB Output is correct
12 Correct 164 ms 197784 KB Output is correct
13 Correct 189 ms 200776 KB Output is correct
14 Correct 50 ms 19028 KB Output is correct
15 Correct 137 ms 129108 KB Output is correct
16 Correct 117 ms 110564 KB Output is correct
17 Correct 88 ms 105552 KB Output is correct
18 Correct 17 ms 4824 KB Output is correct
19 Correct 14 ms 4888 KB Output is correct
20 Correct 16 ms 4700 KB Output is correct
21 Correct 13 ms 4444 KB Output is correct
22 Correct 14 ms 4876 KB Output is correct
23 Correct 17 ms 4696 KB Output is correct
24 Correct 158 ms 160848 KB Output is correct
25 Correct 163 ms 160916 KB Output is correct
26 Correct 157 ms 158800 KB Output is correct
27 Correct 115 ms 118864 KB Output is correct
28 Correct 108 ms 38736 KB Output is correct
29 Correct 47 ms 11980 KB Output is correct