제출 #1256356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256356		wedonttalkanymore	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	255 ms	283564 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, M = 2e6 + 5;

int n, m;
string a[N], b[N], c[N];
int L[M], R[M];
int child[2][M][10], cnt;
vector<int> pre[M];

void add(int type, string s, int pos)
{
    int u = 0;
    if (type) reverse(s.begin(), s.end());
    for (int i = 0; i < s.size(); i++) {
        int k = s[i] - '0';
        if (!child[type][u][k]) child[type][u][k] = ++cnt;
        u = child[type][u][k];
        if (!type) {
            if (!L[u]) L[u] = pos;
            R[u] = pos;
        }
        else pre[u].push_back(pos);
    }
}

int get0(string s)
{
    int u = 0;
    for (int i = 0; i < s.size(); i++) {
        int k = s[i] - '0';
        if (!child[0][u][k]) return -1;
        u = child[0][u][k];
    }
    return u;
}

vector<int> get1(string s)
{
    int u = 0;
    reverse(s.begin(), s.end());
    for (int i = 0; i < s.size(); i++) {
        int k = s[i] - '0';
        if (!child[1][u][k]) return {};
        u = child[1][u][k];
    }
    return pre[u];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i] >> c[i];
    sort(a + 1, a + n + 1);
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        add(0, a[i], i);
        add(1, a[i], i);
    }
    for (int i = 0; i <= cnt; i++) sort(pre[i].begin(), pre[i].end());
    for (int i = 1; i <= m; i++) {
        int val1 = get0(b[i]);
        if (val1 == -1) {
            cout << 0 << '\n';
            continue;
        }
        vector<int> val2 = get1(c[i]);
        if (val2.empty()) {
            cout << 0 << '\n';
            continue;
        }
        int lpos = L[val1], rpos = R[val1];
        if (lpos == 0) {
            cout << 0 << '\n';
            continue;
        }
        int it1 = lower_bound(val2.begin(), val2.end(), lpos) - val2.begin();
        int it2 = upper_bound(val2.begin(), val2.end(), rpos) - val2.begin() - 1;
        cout << max(0LL, it2 - it1 + 1) << '\n';
    }
}

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

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

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