oj.uz

답안 #1104401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104401 2024-10-23T16:01:20 Z Mahog Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1111 ms 573056 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct trie1 {
    vector<unordered_map<char, int>> a;
    vector<int> l, r;
    int n = 0;
    int oo = 1e9;
    unordered_map<char, int> temp;
    
    void start() {
        a.push_back(temp);
        l.push_back(oo);
        r.push_back(0);
    }
    
    void add(string s, int id) {
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (a[pos][s[i]] == 0) {
                a[pos][s[i]] = ++n;
                a.push_back(temp);
                l.push_back(id);
                r.push_back(id);
                pos = n;
            } else {
                pos = a[pos][s[i]];
            }
            r[pos] = id;
        }
    }
    
    pair<int, int> query(string s) {
        int pos = 0;
        for (auto i : s) {
            if (a[pos].find(i) == a[pos].end()) return {-1, -1};
            pos = a[pos][i];
        }
        return {l[pos], r[pos]};
    }
};

struct trie2 {
    vector<unordered_map<char, int>> a;
    vector<vector<int>> b;
    int n = 0;
    unordered_map<char, int> temp;
    
    void start() {
        a.push_back(temp);
        b.push_back({});
    }
    
    void add(string s, int id) {
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (a[pos][s[i]] == 0) {
                a[pos][s[i]] = ++n;
                a.push_back(temp);
                b.push_back({});
                pos = n;
            } else {
                pos = a[pos][s[i]];
            }
            b[pos].push_back(id);
        }
    }
    
    int query(string s) {
        int pos = 0;
        for (auto i : s) {
            if (a[pos].find(i) == a[pos].end()) return -1;
            pos = a[pos][i];
        }
        return pos;
    }
};

const int MAX = 1e5 + 2;
int n, q;
string a[MAX];

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    trie1 chemwy;
    trie2 cheemwy;
    chemwy.start();
    cheemwy.start();
    for (int i = 1; i <= n; i++) {
        chemwy.add(a[i], i);
        reverse(a[i].begin(), a[i].end());
        cheemwy.add(a[i], i);
    }
    for (int i = 1; i <= cheemwy.n; i++) sort(cheemwy.b[i].begin(), cheemwy.b[i].end());
    for (int i = 1; i <= q; i++) {
        string s, t;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        auto [l, r] = chemwy.query(s);
        if (l == -1) {
            cout << 0 << "\n";
            continue;
        }
        int temp = cheemwy.query(t);
        if (temp == -1) {
            cout << 0 << "\n";
            continue;
        }
        int x = upper_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), r) - cheemwy.b[temp].begin() - 1;
        int y = lower_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), l) - cheemwy.b[temp].begin();
        cout << x - y + 1 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

Compilation message

selling_rna.cpp: In member function 'void trie1::add(std::string, int)':
selling_rna.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie2::add(std::string, int)':
selling_rna.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3600 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 3 ms 3408 KB Output is correct
7 Correct 2 ms 3580 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1082 ms 498640 KB Output is correct
2 Correct 1111 ms 471820 KB Output is correct
3 Correct 904 ms 411504 KB Output is correct
4 Correct 639 ms 391660 KB Output is correct
5 Correct 922 ms 566284 KB Output is correct
6 Correct 845 ms 573056 KB Output is correct
7 Correct 167 ms 19016 KB Output is correct
8 Correct 682 ms 341816 KB Output is correct
9 Correct 617 ms 296708 KB Output is correct
10 Correct 488 ms 287916 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 4300 KB Output is correct
2 Correct 20 ms 5240 KB Output is correct
3 Correct 22 ms 4944 KB Output is correct
4 Correct 18 ms 4672 KB Output is correct
5 Correct 20 ms 5136 KB Output is correct
6 Correct 23 ms 4688 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3600 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 3 ms 3408 KB Output is correct
7 Correct 2 ms 3580 KB Output is correct
8 Correct 1082 ms 498640 KB Output is correct
9 Correct 1111 ms 471820 KB Output is correct
10 Correct 904 ms 411504 KB Output is correct
11 Correct 639 ms 391660 KB Output is correct
12 Correct 922 ms 566284 KB Output is correct
13 Correct 845 ms 573056 KB Output is correct
14 Correct 167 ms 19016 KB Output is correct
15 Correct 682 ms 341816 KB Output is correct
16 Correct 617 ms 296708 KB Output is correct
17 Correct 488 ms 287916 KB Output is correct
18 Correct 23 ms 4300 KB Output is correct
19 Correct 20 ms 5240 KB Output is correct
20 Correct 22 ms 4944 KB Output is correct
21 Correct 18 ms 4672 KB Output is correct
22 Correct 20 ms 5136 KB Output is correct
23 Correct 23 ms 4688 KB Output is correct
24 Correct 717 ms 410704 KB Output is correct
25 Correct 922 ms 409384 KB Output is correct
26 Correct 740 ms 402456 KB Output is correct
27 Correct 538 ms 340936 KB Output is correct
28 Correct 305 ms 71420 KB Output is correct
29 Correct 123 ms 11708 KB Output is correct