oj.uz

Submission #1104611

# Submission time Handle Problem Language Result Execution time Memory
1104611 2024-10-24T07:00:48 Z TIN Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 158080 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("avx2")
#include <functional>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
 
int idx(char c) {
    if (c == 'A') return 0;
    if (c == 'U') return 1;
    if (c == 'G') return 2;
    if (c == 'C') return 3;
}
 
struct Trie {
    struct Node {
		Node* child[4];
		int cnt;
        int left_id, right_id;
 
		Node() {
			for (int i = 0; i < 4; i++) child[i] = nullptr;
			cnt = 0;
			left_id = right_id = -1;
		}
	};
 
	Node* root;
 
	Trie() {
        root = new Node();
	}
 
    void add_string(std::string s, int id) {
        Node* p = root;
        for (char c : s) {
            int i = idx(c);
            if (p->child[i] == nullptr) p->child[i] = new Node();
            p = p->child[i];
            if (p->left_id == -1) p->left_id = id;
            p->right_id = id;
            p->cnt++;
        }
    }
 
    void delete_string(std::string s) {
        Node* p = root;
        for (char c : s) {
            int i = idx(c);
            p = p->child[i];
            p->cnt--;
        }
    }
 
    std::pair<int,int> find_range(std::string s) {
        Node* p = root;
        for (char c : s) {
            int i = idx(c);
            if (p->child[i] == nullptr) return {-1, -1};
            p = p->child[i];
        }
        return {p->left_id, p->right_id};
    }
 
    int find_cnt(std::string s) {
        Node* p = root;
        for (char c : s) {
            int i = idx(c);
            if (p->child[i] == nullptr) return 0;
            p = p->child[i];
        }
        return p->cnt;
    }
};
 
Trie trie1, trie2;
 
int main(void) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0); std::cout.tie(0);
    int n, m; std::cin >> n >> m;
    std::vector<std::string> vec(n);
    for (int i = 0; i < n; i++) std::cin >> vec[i];
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i++) {
        trie1.add_string(vec[i], i);
        std::reverse(vec[i].begin(), vec[i].end());
    }
    std::vector<int> ans(m, 0);
    std::vector<std::string> p(m), q(m);
    std::vector<std::pair<std::pair<int,int>,int>> events(m);
    for (int i = 0; i < m; i++) {
        std::cin >> p[i] >> q[i];
        std::reverse(q[i].begin(), q[i].end());
        std::pair<int,int> pi = trie1.find_range(p[i]);
        events[i].first.first = pi.first;
        events[i].first.second = pi.second;
        events[i].second = i;
    }
    std::sort(events.begin(), events.end(), [](auto p1, auto p2) {
        if (p1.first.first / 1000 != p2.first.first / 1000) p1.first.first / 1000 < p2.first.first / 1000;
        return p1.first.second < p2.first.second;
    });
    int L = 1, R = 0;
    for (int i = 0; i < m; i++) {
        int l = events[i].first.first, r = events[i].first.second;
        if (l == -1 && r == -1) continue;
        while (R < r) trie2.add_string(vec[++R], i);
        while (R > r) trie2.delete_string(vec[R--]);
        while (L > l) trie2.add_string(vec[--L], i);
        while (L < l) trie2.delete_string(vec[L++]);
        ans[events[i].second] = trie2.find_cnt(q[events[i].second]);
    }
    for (int i = 0; i < m; i++) std::cout << ans[i] << '\n';
    return 0;
}

Compilation message

selling_rna.cpp: In instantiation of 'main()::<lambda(auto:1, auto:2)> [with auto:1 = std::pair<std::pair<int, int>, int>; auto:2 = std::pair<std::pair<int, int>, int>]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Compare = main()::<lambda(auto:1, auto:2)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >; _Compare = main()::<lambda(auto:1, auto:2)>]'
selling_rna.cpp:104:6:   required from here
selling_rna.cpp:102:83: warning: statement has no effect [-Wunused-value]
  102 |         if (p1.first.first / 1000 != p2.first.first / 1000) p1.first.first / 1000 < p2.first.first / 1000;
      |                                                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int idx(char)':
selling_rna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 128172 KB Output is correct
2 Correct 164 ms 121732 KB Output is correct
3 Correct 1014 ms 126800 KB Output is correct
4 Correct 1054 ms 120904 KB Output is correct
5 Correct 262 ms 156100 KB Output is correct
6 Correct 275 ms 158080 KB Output is correct
7 Correct 257 ms 6728 KB Output is correct
8 Correct 154 ms 96328 KB Output is correct
9 Correct 129 ms 81992 KB Output is correct
10 Correct 98 ms 77384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6224 KB Output is correct
2 Correct 326 ms 4068 KB Output is correct
3 Correct 305 ms 4944 KB Output is correct
4 Correct 18 ms 4176 KB Output is correct
5 Correct 375 ms 4168 KB Output is correct
6 Correct 661 ms 5192 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 164 ms 128172 KB Output is correct
9 Correct 164 ms 121732 KB Output is correct
10 Correct 1014 ms 126800 KB Output is correct
11 Correct 1054 ms 120904 KB Output is correct
12 Correct 262 ms 156100 KB Output is correct
13 Correct 275 ms 158080 KB Output is correct
14 Correct 257 ms 6728 KB Output is correct
15 Correct 154 ms 96328 KB Output is correct
16 Correct 129 ms 81992 KB Output is correct
17 Correct 98 ms 77384 KB Output is correct
18 Correct 27 ms 6224 KB Output is correct
19 Correct 326 ms 4068 KB Output is correct
20 Correct 305 ms 4944 KB Output is correct
21 Correct 18 ms 4176 KB Output is correct
22 Correct 375 ms 4168 KB Output is correct
23 Correct 661 ms 5192 KB Output is correct
24 Correct 177 ms 107336 KB Output is correct
25 Correct 178 ms 110072 KB Output is correct
26 Correct 145 ms 105088 KB Output is correct
27 Execution timed out 1587 ms 105644 KB Time limit exceeded
28 Halted 0 ms 0 KB -