oj.uz

Submission #897386

# Submission time Handle Problem Language Result Execution time Memory
897386 2024-01-03T03:16:59 Z box Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 151 ms 165460 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

vi to_v(string S) {
    vi v(sz(S));
    for (int i = 0; i < sz(S); i++) v[i] = S[i] == 'A' ? 0 : S[i] == 'G' ? 1 : S[i] == 'C' ? 2 : 3;
    return v;
}

struct node {
    int mn, mx, cnt;
    node *kids[4];
    node() {
        mn = INT_MAX, mx = -1;
        cnt = 0;
        for (int i : {0, 1, 2, 3}) kids[i] = NULL;
    }
    void add(int id) {
        mn = min(mn, id);
        mx = max(mx, id);
        cnt++;
    }
} *root;

void ins(const vi s, int id) {
    node *v = root;
    for (int c : s) {
        if (v->kids[c] == NULL) v->kids[c] = new node();
        v = v->kids[c];
        v->add(id);
    }
}

ar<int, 3> qry(const vi s) {
    node *v = root;
    for (int c : s) {
        if (v->kids[c] == NULL) return {-1, -1, 0};
        v = v->kids[c];
    }
    return {v->mn, v->mx, v->cnt};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vi> v(N);
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        v[i] = to_v(s);
    }
    sort(all(v));
    root = new node();
    for (int i = 0; i < N; i++) ins(v[i], i);
    vi ans(M);
    vector<vi> u(M);
    vector<vector<pi>> todo(N);
    for (int i = 0; i < M; i++) {
        string s, t; cin >> s >> t;
        auto [l, r, c] = qry(to_v(s));
        if (!c) continue;
        u[i] = to_v(t);
        reverse(all(u[i]));
        todo[r].push_back({i, 1});
        if (l) todo[l - 1].push_back({i, -1});
    }
    root = new node();
    for (int i = 0; i < N; i++) {
        reverse(all(v[i]));
        ins(v[i], i);
        for (auto [j, c] : todo[i]) ans[j] += c * qry(u[j])[2];
    }
    for (int x : ans) cout << x << '\n';
}

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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 141 ms 136072 KB Output is correct
2 Correct 140 ms 129620 KB Output is correct
3 Correct 123 ms 142220 KB Output is correct
4 Correct 120 ms 136404 KB Output is correct
5 Correct 149 ms 163116 KB Output is correct
6 Correct 145 ms 165460 KB Output is correct
7 Correct 51 ms 20048 KB Output is correct
8 Correct 125 ms 111956 KB Output is correct
9 Correct 118 ms 97332 KB Output is correct
10 Correct 89 ms 87848 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8648 KB Output is correct
2 Correct 20 ms 5980 KB Output is correct
3 Correct 24 ms 7128 KB Output is correct
4 Correct 21 ms 5980 KB Output is correct
5 Correct 21 ms 5980 KB Output is correct
6 Correct 26 ms 7248 KB Output is correct

Subtask #4
40.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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 141 ms 136072 KB Output is correct
9 Correct 140 ms 129620 KB Output is correct
10 Correct 123 ms 142220 KB Output is correct
11 Correct 120 ms 136404 KB Output is correct
12 Correct 149 ms 163116 KB Output is correct
13 Correct 145 ms 165460 KB Output is correct
14 Correct 51 ms 20048 KB Output is correct
15 Correct 125 ms 111956 KB Output is correct
16 Correct 118 ms 97332 KB Output is correct
17 Correct 89 ms 87848 KB Output is correct
18 Correct 27 ms 8648 KB Output is correct
19 Correct 20 ms 5980 KB Output is correct
20 Correct 24 ms 7128 KB Output is correct
21 Correct 21 ms 5980 KB Output is correct
22 Correct 21 ms 5980 KB Output is correct
23 Correct 26 ms 7248 KB Output is correct
24 Correct 141 ms 115216 KB Output is correct
25 Correct 151 ms 117692 KB Output is correct
26 Correct 141 ms 113380 KB Output is correct
27 Correct 122 ms 121260 KB Output is correct
28 Correct 148 ms 40316 KB Output is correct
29 Correct 92 ms 22608 KB Output is correct