제출 #1169404

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

selling_rna

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 5, M = 2e6 + 5, INF = 1e9 + 7;  

int n, m;
string s[N], q[N];
pii range[N];

int tid = 0, r1 = ++tid, r2, mx[M], mn[M], child[M][26];

vector<int> v[M];

int cnt(int id, pii range){
    if(v[id].empty()) return 0;
    return upper_bound(v[id].begin(), v[id].end(), range.second) - lower_bound(v[id].begin(), v[id].end(), range.first);
}

void add(int p, const string &s, int id){
    for(char c : s){
        int nxt = c - 'A';
        if(!child[p][nxt]) child[p][nxt] = ++tid;
        p = child[p][nxt];
        mx[p] = max(mx[p], id);
        mn[p] = min(mn[p], id);
    }
}

void add1(int p, const string &s, int id){
    for(char c : s){
        int nxt = c - 'A';
        if(!child[p][nxt]) child[p][nxt] = ++tid;
        p = child[p][nxt];
        v[p].push_back(id);
    }
}

pii query(int p, const string &pre){
    for(char c : pre){  
        int nxt = c - 'A';
        if(!child[p][nxt]) return {-1, -1};
        p = child[p][nxt];
    }
    return {mn[p], mx[p]};
}

int query1(int p, const string &pre, pii range){
    for(char c : pre){  
        int nxt = c - 'A';
        if(!child[p][nxt]) return 0;
        p = child[p][nxt];
    }
    return cnt(p, range);
}
void solve(){
    for(int i = 0; i < M; i++){
        mx[i] = 0, mn[i] = INF;
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }
    sort(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++){
        add(r1, s[i], i);
        reverse(s[i].begin(), s[i].end());
    }
    for(int i = 1; i <= m; i++){
        string p;
        cin >> p >> q[i];
        reverse(q[i].begin(), q[i].end());
        range[i] = query(r1, p);
    }
    tid = 0, r2 = ++tid;
    memset(child, 0, sizeof child);
    for(int i = 1; i <= n; i++){
        add1(r2, s[i], i);
    }
    for(int i = 1; i <= m; i++){
        int ans = 0;
        if(range[i].first != -1) ans = query1(r2, q[i], range[i]);
        cout << ans << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    #define task "RNA"
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }

    solve();  
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40