제출 #897386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897386		box	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	151 ms	165460 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40