oj.uz

답안 #905864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905864 2024-01-13T05:34:04 Z coldbr3w Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 64 ms 102284 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
struct Trie{
    struct node{
        ll c[10];
        ll l, r;
        vector<ll>range;
    }; node x[N];
    ll cur;
    Trie() : cur(0){
        memset(x[0].c, -1, sizeof(x[0]));
        x[0].l = inf;
        x[0].r = -inf;
    }
    ll init(){
        cur++;
        memset(x[cur].c, -1, sizeof(x[cur]));
        x[cur].l = inf, x[0].r = -inf;
        return cur;
    }  
    void add(string s, ll idx){
        ll pos = 0;
        for(auto f : s){
            ll c = f - 'A';
            if(x[pos].c[c] == -1) x[pos].c[c] = init();
            pos = x[pos].c[c];
            x[pos].range.pb(idx);
            x[pos].l = min(idx, x[pos].l);
            x[pos].r = max(idx, x[pos].r);
        }
    }
    pll find_range(string s){
        ll pos = 0;
        for(auto f : s){
            ll c = f - 'A';
            pos = x[pos].c[c];
        }
        return {x[pos].l, x[pos].r};
    }
    vector<ll>dfs(string s){
        ll pos = 0;
        vector<ll>tmp;
        for(auto f : s){
            ll c = f - 'A';
            pos = x[pos].c[c];
            if(pos == -1) return tmp;
        }
        return x[pos].range;
    }
};
string cnv(string s){
    string ans = s;
    for(int i = 0; i < ans.size();i++){
        if(ans[i] == 'C') ans[i] = 'B';
        else if(ans[i] == 'G') ans[i] = 'C';
        else if(ans[i] == 'U') ans[i] = 'D'; 
    }
    return ans;
}
Trie rev, tr;
void to_nho_cau(){
    ll n,m; cin >> n >> m;
    vector<string>v;
    for(int i = 1; i <= n;i++){
        string s; cin >> s;
        s = cnv(s);
        v.pb(s);
    }
    sort(all(v));
    for(int i = 0; i < v.size();i++){
        tr.add(v[i], i);
        string t = v[i]; reverse(all(t));
        rev.add(t, i);
    }
    while(m--){
        string p,q; cin >> p >> q;
        p = cnv(p), q = cnv(q);    
        reverse(all(q));
        pll cur = tr.find_range(p);
        ll l = cur.F, r = cur.S;
        vector<ll>res = rev.dfs(q);
        if(!res.size() || l > r){
            cout << 0 << '\ns';
            continue;
        }
        ll high = upper_bound(all(res), r) - res.begin();
        ll low = lower_bound(all(res), l) - res.begin();
        cout << high - low << '\n';
    }
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;   
    //cin >> t;
    while(t--) to_nho_cau();
}

Compilation message

selling_rna.cpp:97:26: warning: multi-character character constant [-Wmultichar]
   97 |             cout << 0 << '\ns';
      |                          ^~~~~
selling_rna.cpp: In function 'std::string cnv(std::string)':
selling_rna.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < ans.size();i++){
      |                    ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void to_nho_cau()':
selling_rna.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 95684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 64 ms 102284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 60 ms 99492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 95684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -