답안 #1104606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104606	2024-10-24T06:52:14 Z	TIN	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1500 ms	158280 KB

selling_rna

#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

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

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

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

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