oj.uz

Submission #1104613

# Submission time Handle Problem Language Result Execution time Memory
1104613 2024-10-24T07:10:16 Z TIN Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 230 ms 158216 KB 
#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.second / 320 != p2.first.second / 320) p1.first.second / 320 < p2.first.second / 320;
        return p1.first.first < p2.first.first;
    });
    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 (L > l) trie2.add_string(vec[--L], i);
        while (R > r) trie2.delete_string(vec[R--]);
        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:102:6:   required from here
selling_rna.cpp:100:83: warning: statement has no effect [-Wunused-value]
  100 |         if (p1.first.second / 320 != p2.first.second / 320) p1.first.second / 320 < p2.first.second / 320;
      |                                                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int idx(char)':
selling_rna.cpp:12:1: warning: control reaches end of non-void function [-Wreturn-type]
   12 | }
      | ^

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 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 128072 KB Output is correct
2 Correct 163 ms 121928 KB Output is correct
3 Correct 230 ms 126692 KB Output is correct
4 Correct 193 ms 120904 KB Output is correct
5 Correct 213 ms 155976 KB Output is correct
6 Correct 223 ms 158216 KB Output is correct
7 Correct 33 ms 6736 KB Output is correct
8 Correct 129 ms 96328 KB Output is correct
9 Correct 110 ms 81992 KB Output is correct
10 Correct 91 ms 77392 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6216 KB Output is correct
2 Correct 16 ms 4176 KB Output is correct
3 Correct 20 ms 4944 KB Output is correct
4 Correct 15 ms 4176 KB Output is correct
5 Correct 17 ms 4156 KB Output is correct
6 Correct 24 ms 5200 KB Output is correct

Subtask #4
40.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 336 KB Output is correct
8 Correct 141 ms 128072 KB Output is correct
9 Correct 163 ms 121928 KB Output is correct
10 Correct 230 ms 126692 KB Output is correct
11 Correct 193 ms 120904 KB Output is correct
12 Correct 213 ms 155976 KB Output is correct
13 Correct 223 ms 158216 KB Output is correct
14 Correct 33 ms 6736 KB Output is correct
15 Correct 129 ms 96328 KB Output is correct
16 Correct 110 ms 81992 KB Output is correct
17 Correct 91 ms 77392 KB Output is correct
18 Correct 22 ms 6216 KB Output is correct
19 Correct 16 ms 4176 KB Output is correct
20 Correct 20 ms 4944 KB Output is correct
21 Correct 15 ms 4176 KB Output is correct
22 Correct 17 ms 4156 KB Output is correct
23 Correct 24 ms 5200 KB Output is correct
24 Correct 134 ms 107292 KB Output is correct
25 Correct 145 ms 110152 KB Output is correct
26 Correct 141 ms 105288 KB Output is correct
27 Correct 145 ms 106068 KB Output is correct
28 Correct 104 ms 34632 KB Output is correct
29 Correct 58 ms 15176 KB Output is correct