Submission #445830

#	Time	Username	Problem	Language	Result	Execution time	Memory
445830		JovanB	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	754 ms	819016 KiB

selling_rna

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

using ll = long long;
using ld = long double;

const int N = 100000;

int x[N+5];
int y[N+5];

const int MAXC = 4000000;
int gde[MAXC+5][26];

int tjm;

vector <pair <int, int>> graf[MAXC+5];
vector <int> koji[MAXC+5];
vector <int> queries[MAXC+5];

void trie_add(int t, int ind, const string &s){
    int v = 0;
    for(int i=0; i<s.size(); i++){
        int x = s[i] - 'A';
        if(!gde[v][x]){
            gde[v][x] = ++tjm;
            graf[v].push_back({tjm, x});
        }
        v = gde[v][x];
    }
    if(t == 1) koji[v].push_back(ind);
    else queries[v].push_back(ind);
}

int xl[N+5], yl[N+5], xr[N+5], yr[N+5];

void dfs(int t, int v){
    int in = ++tjm;
    for(auto c : koji[v]){
        if(t == 1) x[c] = in;
        else y[c] = in;
    }
    for(auto c : graf[v]) dfs(t, c.first);
    int out = tjm;
    for(auto c : queries[v]){
        if(t == 1){
            xl[c] = in, xr[c] = out;
        }
        else{
            yl[c] = in, yr[c] = out;
        }
    }
    queries[v].clear();
    koji[v].clear();
    for(auto c : graf[v]){
        gde[v][c.second] = 0;
    }
    graf[v].clear();
}

string s[N+5];
string qpref[N+5];
string qsuf[N+5];

int bit[MAXC+5];

void bit_add(int x){
    while(x <= MAXC){
        bit[x]++;
        x += x & -x;
    }
}

int bit_get(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

const int INF = 1000000000;

vector <int> upds[MAXC+5];
vector <pair <pair <int, int>, int>> quers[MAXC+5];

int res[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> s[i];
        trie_add(1, i, s[i]);
    }
    for(int i=1; i<=m; i++){
        cin >> qpref[i] >> qsuf[i];
        trie_add(2, i, qpref[i]);
    }
    dfs(1, 0);
    for(int i=1; i<=n; i++){
        reverse(s[i].begin(), s[i].end());
        trie_add(1, i, s[i]);
    }
    for(int i=1; i<=m; i++){
        reverse(qsuf[i].begin(), qsuf[i].end());
        trie_add(2, i, qsuf[i]);
    }
    tjm = 0;
    dfs(2, 0);
    for(int i=1; i<=n; i++){
        upds[y[i]].push_back(x[i]);
    }
    for(int i=1; i<=m; i++){
        quers[yr[i]].push_back({{xl[i], xr[i]}, i});
        quers[yl[i] - 1].push_back({{xl[i], xr[i]}, -i});
    }
    for(int i=1; i<=MAXC; i++){
        for(auto c : upds[i]) bit_add(c);
        for(auto c : quers[i]){
            int ind = c.second;
            int kf = 1;
            if(ind < 0){
                ind = -ind;
                kf = -1;
            }
            res[ind] += kf*(bit_get(c.first.second) - bit_get(c.first.first - 1));
        }
    }
    for(int i=1; i<=m; i++) cout << res[i] << "\n";
    return 0;
}

Compilation message (stderr)

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

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