oj.uz

Submission #1086809

# Submission time Handle Problem Language Result Execution time Memory
1086809 2024-09-11T14:00:53 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 179 ms 200788 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 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3488 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 194388 KB Output is correct
2 Correct 178 ms 184732 KB Output is correct
3 Correct 121 ms 142228 KB Output is correct
4 Correct 116 ms 135764 KB Output is correct
5 Correct 164 ms 197800 KB Output is correct
6 Correct 166 ms 200788 KB Output is correct
7 Correct 49 ms 19024 KB Output is correct
8 Correct 143 ms 129108 KB Output is correct
9 Correct 116 ms 110680 KB Output is correct
10 Correct 101 ms 105496 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4824 KB Output is correct
2 Correct 14 ms 4956 KB Output is correct
3 Correct 17 ms 4696 KB Output is correct
4 Correct 13 ms 4444 KB Output is correct
5 Correct 15 ms 4956 KB Output is correct
6 Correct 18 ms 4700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3488 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 179 ms 194388 KB Output is correct
9 Correct 178 ms 184732 KB Output is correct
10 Correct 121 ms 142228 KB Output is correct
11 Correct 116 ms 135764 KB Output is correct
12 Correct 164 ms 197800 KB Output is correct
13 Correct 166 ms 200788 KB Output is correct
14 Correct 49 ms 19024 KB Output is correct
15 Correct 143 ms 129108 KB Output is correct
16 Correct 116 ms 110680 KB Output is correct
17 Correct 101 ms 105496 KB Output is correct
18 Correct 20 ms 4824 KB Output is correct
19 Correct 14 ms 4956 KB Output is correct
20 Correct 17 ms 4696 KB Output is correct
21 Correct 13 ms 4444 KB Output is correct
22 Correct 15 ms 4956 KB Output is correct
23 Correct 18 ms 4700 KB Output is correct
24 Correct 176 ms 160904 KB Output is correct
25 Correct 172 ms 161040 KB Output is correct
26 Correct 162 ms 158804 KB Output is correct
27 Correct 110 ms 118708 KB Output is correct
28 Correct 109 ms 38724 KB Output is correct
29 Correct 48 ms 11984 KB Output is correct