oj.uz

Submission #1104606

# Submission time Handle Problem Language Result Execution time Memory
1104606 2024-10-24T06:52:14 Z TIN Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 158280 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 / 320 != p2.first.first / 320) p1.first.first / 320 < p2.first.first / 320;
        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:80: warning: statement has no effect [-Wunused-value]
  102 |         if (p1.first.first / 320 != p2.first.first / 320) p1.first.first / 320 < p2.first.first / 320;
      |                                                           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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 432 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 130428 KB Output is correct
2 Correct 149 ms 125676 KB Output is correct
3 Correct 972 ms 126792 KB Output is correct
4 Correct 998 ms 123128 KB Output is correct
5 Correct 250 ms 157512 KB Output is correct
6 Correct 258 ms 158280 KB Output is correct
7 Correct 238 ms 6728 KB Output is correct
8 Correct 132 ms 96328 KB Output is correct
9 Correct 128 ms 82204 KB Output is correct
10 Correct 99 ms 78744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6632 KB Output is correct
2 Correct 346 ms 4064 KB Output is correct
3 Correct 308 ms 5412 KB Output is correct
4 Correct 19 ms 4176 KB Output is correct
5 Correct 411 ms 4424 KB Output is correct
6 Correct 724 ms 4944 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 432 KB Output is correct
8 Correct 159 ms 130428 KB Output is correct
9 Correct 149 ms 125676 KB Output is correct
10 Correct 972 ms 126792 KB Output is correct
11 Correct 998 ms 123128 KB Output is correct
12 Correct 250 ms 157512 KB Output is correct
13 Correct 258 ms 158280 KB Output is correct
14 Correct 238 ms 6728 KB Output is correct
15 Correct 132 ms 96328 KB Output is correct
16 Correct 128 ms 82204 KB Output is correct
17 Correct 99 ms 78744 KB Output is correct
18 Correct 29 ms 6632 KB Output is correct
19 Correct 346 ms 4064 KB Output is correct
20 Correct 308 ms 5412 KB Output is correct
21 Correct 19 ms 4176 KB Output is correct
22 Correct 411 ms 4424 KB Output is correct
23 Correct 724 ms 4944 KB Output is correct
24 Correct 188 ms 107336 KB Output is correct
25 Correct 197 ms 110152 KB Output is correct
26 Correct 166 ms 105288 KB Output is correct
27 Execution timed out 1579 ms 105760 KB Time limit exceeded
28 Halted 0 ms 0 KB -