oj.uz

Submission #1065728

# Submission time Handle Problem Language Result Execution time Memory
1065728 2024-08-19T11:19:38 Z VMaksimoski008 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 313684 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 && b <= x[3] && x[2] <= c && d <= 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 308 ms 249680 KB Output is correct
2 Correct 362 ms 240464 KB Output is correct
3 Correct 326 ms 250196 KB Output is correct
4 Correct 359 ms 238392 KB Output is correct
5 Correct 354 ms 309076 KB Output is correct
6 Correct 379 ms 313684 KB Output is correct
7 Correct 170 ms 8256 KB Output is correct
8 Correct 300 ms 187564 KB Output is correct
9 Correct 344 ms 158552 KB Output is correct
10 Correct 251 ms 151712 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 308 ms 249680 KB Output is correct
9 Correct 362 ms 240464 KB Output is correct
10 Correct 326 ms 250196 KB Output is correct
11 Correct 359 ms 238392 KB Output is correct
12 Correct 354 ms 309076 KB Output is correct
13 Correct 379 ms 313684 KB Output is correct
14 Correct 170 ms 8256 KB Output is correct
15 Correct 300 ms 187564 KB Output is correct
16 Correct 344 ms 158552 KB Output is correct
17 Correct 251 ms 151712 KB Output is correct
18 Execution timed out 1555 ms 4052 KB Time limit exceeded
19 Halted 0 ms 0 KB -