답안 #1104610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104610	2024-10-24T06:59:44 Z	TIN	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1500 ms	158284 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.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:102:6:   required from here
selling_rna.cpp:100:83: warning: statement has no effect [-Wunused-value]
  100 |         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: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	504 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	144 ms	128184 KB	Output is correct
2	Correct	141 ms	121928 KB	Output is correct
3	Correct	958 ms	126792 KB	Output is correct
4	Correct	1014 ms	120904 KB	Output is correct
5	Correct	269 ms	155772 KB	Output is correct
6	Correct	283 ms	158284 KB	Output is correct
7	Correct	255 ms	6736 KB	Output is correct
8	Correct	120 ms	96328 KB	Output is correct
9	Correct	112 ms	81876 KB	Output is correct
10	Correct	87 ms	77384 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	6224 KB	Output is correct
2	Correct	334 ms	4060 KB	Output is correct
3	Correct	316 ms	4944 KB	Output is correct
4	Correct	16 ms	4176 KB	Output is correct
5	Correct	394 ms	4176 KB	Output is correct
6	Correct	747 ms	5192 KB	Output is correct

Subtask #4

0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	504 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	144 ms	128184 KB	Output is correct
9	Correct	141 ms	121928 KB	Output is correct
10	Correct	958 ms	126792 KB	Output is correct
11	Correct	1014 ms	120904 KB	Output is correct
12	Correct	269 ms	155772 KB	Output is correct
13	Correct	283 ms	158284 KB	Output is correct
14	Correct	255 ms	6736 KB	Output is correct
15	Correct	120 ms	96328 KB	Output is correct
16	Correct	112 ms	81876 KB	Output is correct
17	Correct	87 ms	77384 KB	Output is correct
18	Correct	21 ms	6224 KB	Output is correct
19	Correct	334 ms	4060 KB	Output is correct
20	Correct	316 ms	4944 KB	Output is correct
21	Correct	16 ms	4176 KB	Output is correct
22	Correct	394 ms	4176 KB	Output is correct
23	Correct	747 ms	5192 KB	Output is correct
24	Correct	190 ms	107608 KB	Output is correct
25	Correct	171 ms	110152 KB	Output is correct
26	Correct	142 ms	105288 KB	Output is correct
27	Execution timed out	1577 ms	105812 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-