Submission #1104608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104608		TIN	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1584 ms	128328 KiB

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++;
        }
    }

    bool delete_string_recursive(Node* p, std::string& s, int t) {
        if (t != (int) s.size()) {
            int i = idx(s[t]);
            bool isChildDel = delete_string_recursive(p->child[i], s, t + 1);
            if (isChildDel) p->child[i] = nullptr;
        }
        if (p != root) {
            p->cnt--;
            if (p->cnt == 0) {
                delete(p);
                return true;
            }
        }
        return false;
    }

    void delete_string(std::string s) {
        delete_string_recursive(root, s, 0);
    }

    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 (stderr)

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:113:6:   required from here
selling_rna.cpp:111:80: warning: statement has no effect [-Wunused-value]
  111 |         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:12:1: warning: control reaches end of non-void function [-Wreturn-type]
   12 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40