제출 #1048155

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

selling_rna

#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int N = 1e5 + 2;
const int M = 2e6 + 5;
const int mx = 2e6;

int n, m, cur = 0, cnt = 0;
string s[N];
int in[2][26 * N], out[2][26 * N];
int x[2][N], ans[N];
char xet[] = {'C', 'U', 'G', 'A'};
struct Node
{
    int child[26];
    vector<int> exist;
} nodes[2][26 * N];
vector<int> ask[26 * N];

int new_node(int hihi)
{
    cur++;
    memset(nodes[hihi][cur].child, -1, sizeof(nodes[hihi][cur].child));
    return cur;
}

void add_string(string s, int j, int hihi)
{
    int pos = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'A';
        if (nodes[hihi][pos].child[c] == -1)
            nodes[hihi][pos].child[c] = new_node(hihi);
        pos = nodes[hihi][pos].child[c];
    }
    nodes[hihi][pos].exist.push_back(j);
}

void dfs(int pos, int hihi)
{
    in[hihi][pos] = out[hihi][pos] = ++cnt;
    for (int i = 0; i < 4; i++)
    {
        int c = xet[i] - 'A';
        if(nodes[hihi][pos].child[c] == -1)
            continue;
       dfs(nodes[hihi][pos].child[c], hihi);
    }
    out[hihi][pos] = cnt;
    for(auto i : nodes[hihi][pos].exist)
        x[hihi][i] = in[hihi][pos];
//    cout << hihi << " " << pos << " " << in[hihi][pos] << '\n';
    return;
}

pair<int, int> find_string(string s, int hihi)
{
    int pos = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'A';
        if(nodes[hihi][pos].child[c] == -1)
            return {-1,- 1};
        pos = nodes[hihi][pos].child[c];
    }
//    cout << s << " " << hihi << " " << pos << '\n';
    return {in[hihi][pos], out[hihi][pos]};
}

vector<int> vt[M];
vector<tuple<int, int, int>> add[M];
int bit[M];

int get(int p)
{
    int idx = p, ans = 0;
    while (idx > 0) {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}

void update(int u, int v)
{
    int idx = u;
    while (idx <= mx)
    {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    memset(nodes[0][0].child, -1, sizeof(nodes[0][0].child));

    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        add_string(s[i], i, 0);
    }

    dfs(0, 0);

    cur = cnt = 0;
    memset(nodes[1][0].child, -1, sizeof(nodes[1][0].child));

    for(int i = 1; i <= n; i++)
    {
        reverse(s[i].begin(), s[i].end());
        add_string(s[i], i, 1);
    }

    dfs(0, 1);

    for(int i = 1; i <= n; i++)
        vt[x[0][i]].push_back(x[1][i]);//, cout << x[0][i] << " " << x[1][i] << '\n';

    memset(ans, -1, sizeof ans);

    for(int i = 1; i <= m; i++)
    {
        string p, q;
        cin >> p >> q;
        reverse(q.begin(), q.end());
        pair<int, int> tmp = find_string(p, 0), tmp1 = find_string(q, 1);
//        cout << tmp.fi << " " << tmp.se << " " << tmp1.fi << " " << tmp1.se << '\n';
        if(tmp.fi != -1 && tmp1.fi != -1)
        {
            add[tmp.fi - 1].push_back({tmp1.fi, tmp1.se, i});
            add[tmp.se].push_back({tmp1.fi, tmp1.se, i});
        }
    }
    for(int i = 1; i <= mx; i++)
    {
        for(auto j : vt[i])
            update(j, 1);
        for(auto [j, k, l] : add[i])
        {
            if(ans[l] == -1)
                ans[l] = get(k) - get(j - 1);
            else
                ans[l] = get(k) - get(j - 1) - ans[l];
//                cout << i << " " << j << " " << k << " " << ans[l] << '\n';
        }
    }
    for(int i = 1; i <= m; i++)
        if(ans[i] == -1)
            cout << 0 << '\n';
        else
            cout << ans[i] << '\n';
    return 0;
}

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

selling_rna.cpp: In function 'void add_string(std::string, int, int)':
selling_rna.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> find_string(std::string, int)':
selling_rna.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

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