Submission #109176

#	Time	Username	Problem	Language	Result	Execution time	Memory
109176		popovicirobert	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1579 ms	428632 KiB

selling_rna

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

struct Trie {

    Trie *son[26];
    int sz;
    vector <int> pos;

    Trie() {
        memset(son, NULL, sizeof(son));
        sz = 0;
    }

};

Trie *root1 = new Trie;
Trie *root2 = new Trie;

void add(Trie *nod, string &str, int p, int id) {
    if(p == str.size()) {
        nod -> sz++;
        nod -> pos.push_back(id);
    }
    else {
        int ch = str[p] - 'A';
        if(nod -> son[ch] == NULL) {
            nod -> son[ch] = new Trie;
        }
        add(nod -> son[ch], str, p + 1, id);
        nod -> sz++;
    }
}

void dfs(Trie *nod, string &str, int &id) {
    int num = 0;
    for(int ch = 0; ch < 26; ch++) {
        if(nod -> son[ch] != NULL) {
            num++;
            str.push_back(ch + 'A');
            dfs(nod -> son[ch], str, id);
            str.pop_back();
        }
    }

    if(num == 0) {
        reverse(str.begin(), str.end());
        add(root2, str, 0, ++id);
        reverse(str.begin(), str.end());
        return ;
    }
}

void query(Trie *nod, string &str, int p, pair <int, int> &cur) {
    if(nod == NULL) {
        cur = {-1, -1};
        return ;
    }

    if(p == str.size()) {
        cur.second = cur.first + nod -> sz;
        cur.first++;
    }
    else {
        char ch = str[p] - 'A';
        for(int i = 0; i < ch; i++) {
            if(nod -> son[i] != NULL) {
                cur.first += nod -> son[i] -> sz;
            }
        }
        query(nod -> son[ch], str, p + 1, cur);
    }
}

void dfs1(Trie *nod, vector <int> &arr) {
    int num = 0;
    for(int ch = 0; ch < 26; ch++) {
        if(nod -> son[ch] != NULL) {
            num++;
            dfs1(nod -> son[ch], arr);
        }
    }

    if(num == 0) {
        for(auto it : nod -> pos) {
            arr.push_back(it);
        }
        return ;
    }
}


struct Query {
    int pos, val;
    char sign;
    int id;
    bool operator <(const Query &other) const {
        return pos < other.pos;
    }
};


struct Fenwick {
    vector <int> aib;
    int n;
    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }
    inline void update(int pos, int val) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }
    inline int query(int pos) {
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }
    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
};


/*void print(Trie *nod) {
    for(auto it : nod -> pos) {
        cerr << it << " ";
    }
    cerr << "\n";
    for(int ch = 0; ch < 26; ch++) {
        if(nod -> son[ch] != NULL) {
            print(nod -> son[ch]);
        }
    }
}*/


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for(i = 1; i <= n; i++) {
        string str;
        cin >> str;
        add(root1, str, 0, i);
    }

    string str;
    int id = 0;
    dfs(root1, str, id);

    vector <int> arr(1);
    dfs1(root2, arr);

    vector <Query> qry;

    for(i = 1; i <= m; i++) {
        string a, b;
        cin >> a >> b;

        pair <int, int> cur1, cur2;
        cur1 = cur2 = {0, 0};

        query(root1, a, 0, cur1);
        query(root2, b, 0, cur2);

        qry.push_back({cur2.first - 1, cur1.first - 1, 1, i});
        qry.push_back({cur2.first - 1, cur1.second, -1, i});
        qry.push_back({cur2.second, cur1.first - 1, -1, i});
        qry.push_back({cur2.second, cur1.second, 1, i});
    }

    Fenwick fen; fen.init(n);
    sort(qry.begin(), qry.end());

    vector <int> sol(m + 1);
    int pos = 0, sz = qry.size();

    for(i = 0; i <= n; i++) {
        if(i > 0) {
            fen.update(arr[i], 1);
        }
        while(pos < sz && qry[pos].pos <= i) {
            sol[qry[pos].id] += qry[pos].sign * fen.query(qry[pos].val);
            pos++;
        }
    }

    for(i = 1; i <= m; i++) {
        cout << sol[i] << "\n";
    }

    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:17:38: warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]
         memset(son, NULL, sizeof(son));
                                      ^
selling_rna.cpp: In function 'void add(Trie*, std::__cxx11::string&, int, int)':
selling_rna.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == str.size()) {
        ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void query(Trie*, std::__cxx11::string&, int, std::pair<int, int>&)':
selling_rna.cpp:66:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == str.size()) {
        ~~^~~~~~~~~~~~~
selling_rna.cpp:77:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         query(nod -> son[ch], str, p + 1, cur);
                            ^

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