답안 #1104613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104613	2024-10-24T07:10:16 Z	TIN	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	230 ms	158216 KB

selling_rna

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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