oj.uz

Submission #1048155

# Submission time Handle Problem Language Result Execution time Memory
1048155 2024-08-08T03:05:35 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 358 ms 838228 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 810252 KB Output is correct
2 Correct 266 ms 810324 KB Output is correct
3 Correct 307 ms 810516 KB Output is correct
4 Correct 266 ms 810320 KB Output is correct
5 Correct 237 ms 810228 KB Output is correct
6 Correct 240 ms 810324 KB Output is correct
7 Correct 253 ms 810324 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 837716 KB Output is correct
2 Correct 313 ms 837504 KB Output is correct
3 Correct 312 ms 830800 KB Output is correct
4 Correct 308 ms 830032 KB Output is correct
5 Correct 358 ms 837692 KB Output is correct
6 Correct 358 ms 838228 KB Output is correct
7 Correct 268 ms 815672 KB Output is correct
8 Correct 331 ms 830036 KB Output is correct
9 Correct 345 ms 827984 KB Output is correct
10 Correct 289 ms 826452 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 813744 KB Output is correct
2 Correct 265 ms 812884 KB Output is correct
3 Correct 291 ms 813516 KB Output is correct
4 Correct 249 ms 812884 KB Output is correct
5 Correct 264 ms 812628 KB Output is correct
6 Correct 262 ms 812984 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 810252 KB Output is correct
2 Correct 266 ms 810324 KB Output is correct
3 Correct 307 ms 810516 KB Output is correct
4 Correct 266 ms 810320 KB Output is correct
5 Correct 237 ms 810228 KB Output is correct
6 Correct 240 ms 810324 KB Output is correct
7 Correct 253 ms 810324 KB Output is correct
8 Correct 333 ms 837716 KB Output is correct
9 Correct 313 ms 837504 KB Output is correct
10 Correct 312 ms 830800 KB Output is correct
11 Correct 308 ms 830032 KB Output is correct
12 Correct 358 ms 837692 KB Output is correct
13 Correct 358 ms 838228 KB Output is correct
14 Correct 268 ms 815672 KB Output is correct
15 Correct 331 ms 830036 KB Output is correct
16 Correct 345 ms 827984 KB Output is correct
17 Correct 289 ms 826452 KB Output is correct
18 Correct 266 ms 813744 KB Output is correct
19 Correct 265 ms 812884 KB Output is correct
20 Correct 291 ms 813516 KB Output is correct
21 Correct 249 ms 812884 KB Output is correct
22 Correct 264 ms 812628 KB Output is correct
23 Correct 262 ms 812984 KB Output is correct
24 Correct 331 ms 835160 KB Output is correct
25 Correct 317 ms 836432 KB Output is correct
26 Correct 332 ms 834620 KB Output is correct
27 Correct 315 ms 828752 KB Output is correct
28 Correct 325 ms 824740 KB Output is correct
29 Correct 308 ms 818004 KB Output is correct