oj.uz

Submission #1065729

# Submission time Handle Problem Language Result Execution time Memory
1065729 2024-08-19T11:20:38 Z VMaksimoski008 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 311288 KB 
#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct Node {
    int in, out;
    map<char, Node*> mp;

    Node() {}
};

struct Trie {
    Node *root;
    int timer = 0;

    Trie() { root = new Node(); }
    ~Trie() { delete root; }

    void insert(string s) {
        Node *u = root;
        for(char &ch : s) {
            if(!u->mp.count(ch)) u->mp[ch] = new Node();
            u = u->mp[ch];
        }
    }

    pii search(string s) {
        Node *u = root;
        for(char &ch : s) {
            if(!u->mp.count(ch)) return { -1, -1 };
            u = u->mp[ch];
        }
        return { u->in, u->out };
    }

    void dfs(Node *u) {
        u->in = timer++;
        for(auto &x : u->mp) dfs(x.second);
        u->out = timer;
    }

    void callDFS() {
        dfs(root);
    }
};

struct BIT {
    int n;
    vector<int> tree;

    BIT(int _n) : n(_n+50), tree(_n+100) {}

    void update(int p, int v) { for(p++; p<n; p+=p&-p) tree[p] += v; }
    int query(int p) { int ans = 0; for(p++; p; p-=p&-p) ans += tree[p]; return ans;}
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q;
    cin >> n >> q;

    Trie trie, rev_trie;
    vector<string> vec(n);
    for(int i=0; i<n; i++) {
        cin >> vec[i];
        trie.insert(vec[i]);
        reverse(vec[i].begin(), vec[i].end());
        rev_trie.insert(vec[i]);
        reverse(vec[i].begin(), vec[i].end());
    }

    trie.callDFS();
    rev_trie.callDFS();

    vector<array<int, 5> > qus;
    vector<int> ans(q);
    for(int i=0; i<q; i++) {
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());
        auto [in1, out1] = trie.search(a);
        auto [in2, out2] = rev_trie.search(b);
        if(in1 == -1 || in2 == -1) continue;
        qus.push_back({ i, in1, in2, out1, out2 });
    }

    vector<array<int, 4> > ptr(n);
    for(int i=0; i<n; i++) {
        ptr[i][0] = trie.search(vec[i]).first;
        ptr[i][1] = trie.search(vec[i]).second;
        reverse(vec[i].begin(), vec[i].end());
        ptr[i][2] = rev_trie.search(vec[i]).first;
        ptr[i][3] = rev_trie.search(vec[i]).second;
    }

    for(auto &x : qus) {
        // cout << x[1] << " " << x[2] << " " << x[3] << " " << x[4] << '\n';
        for(auto &[a, b, c, d] : ptr)
            if(x[1] <= a && a < x[3] && x[2] <= c && c < x[4]) ans[x[0]]++;        
    }

    for(int &x : ans) cout << x << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 249684 KB Output is correct
2 Correct 371 ms 236600 KB Output is correct
3 Correct 352 ms 246180 KB Output is correct
4 Correct 364 ms 234324 KB Output is correct
5 Correct 343 ms 306616 KB Output is correct
6 Correct 376 ms 311288 KB Output is correct
7 Correct 166 ms 2640 KB Output is correct
8 Correct 318 ms 181472 KB Output is correct
9 Correct 346 ms 152656 KB Output is correct
10 Correct 222 ms 148308 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1544 ms 4048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 270 ms 249684 KB Output is correct
9 Correct 371 ms 236600 KB Output is correct
10 Correct 352 ms 246180 KB Output is correct
11 Correct 364 ms 234324 KB Output is correct
12 Correct 343 ms 306616 KB Output is correct
13 Correct 376 ms 311288 KB Output is correct
14 Correct 166 ms 2640 KB Output is correct
15 Correct 318 ms 181472 KB Output is correct
16 Correct 346 ms 152656 KB Output is correct
17 Correct 222 ms 148308 KB Output is correct
18 Execution timed out 1544 ms 4048 KB Time limit exceeded
19 Halted 0 ms 0 KB -