Submission #109198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
109198	2019-05-05T12:22:58 Z	popovicirobert	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1352 ms	197080 KB

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 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;
    }
};

struct Trie {

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

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

};

int ind[256], vals[256];

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 = ind[str[p]];
        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) {
    reverse(str.begin(), str.end());
    for(auto it : nod -> pos) {
        add(root2, str, 0, ++id);
    }
    reverse(str.begin(), str.end());

    for(int ch = 0; ch < 4; ch++) {
        if(nod -> son[ch] != NULL) {
            str.push_back(vals[ch]);
            dfs(nod -> son[ch], str, id);
            str.pop_back();
        }
    }
}

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

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


void dfs1(Trie *nod, vector <int> &arr) {
    for(auto it : nod -> pos) {
        arr.push_back(it);
    }

    for(int ch = 0; ch < 4; ch++) {
        if(nod -> son[ch] != NULL) {
            dfs1(nod -> son[ch], arr);
        }
    }
}


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


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);

    ind['A'] = 0;   vals[0] = 'A';
    ind['C'] = 1;   vals[1] = 'C';
    ind['G'] = 2;   vals[2] = 'G';
    ind['U'] = 3;   vals[3] = 'U';

    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;

        reverse(b.begin(), b.end());

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

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

        if(cur1.first <= cur1.second && cur2.first <= cur2.second) {

            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});

        }
        //cerr << cur1.first << " " << cur1.second << " " << cur2.first << " " << cur2.second << "\n";
    }

    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;
}



/*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]);
        }
    }
}*/

Compilation message

selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:38: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:50:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == str.size()) {
        ~~^~~~~~~~~~~~~
selling_rna.cpp:55:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         int ch = ind[str[p]];
                            ^
selling_rna.cpp: In function 'void dfs(Trie*, std::__cxx11::string&, int&)':
selling_rna.cpp:66:14: warning: unused variable 'it' [-Wunused-variable]
     for(auto it : nod -> pos) {
              ^~
selling_rna.cpp: In function 'void query(Trie*, std::__cxx11::string&, int, std::pair<int, int>&)':
selling_rna.cpp:86:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == str.size()) {
        ~~^~~~~~~~~~~~~
selling_rna.cpp:91:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         int ch = ind[str[p]];
                            ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	299 ms	155656 KB	Output is correct
2	Correct	348 ms	147592 KB	Output is correct
3	Correct	1352 ms	155532 KB	Output is correct
4	Correct	876 ms	150152 KB	Output is correct
5	Correct	519 ms	194324 KB	Output is correct
6	Correct	526 ms	197080 KB	Output is correct
7	Correct	75 ms	7084 KB	Output is correct
8	Correct	478 ms	118996 KB	Output is correct
9	Correct	379 ms	100628 KB	Output is correct
10	Correct	330 ms	95496 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	5360 KB	Output is correct
2	Correct	25 ms	3444 KB	Output is correct
3	Correct	35 ms	5384 KB	Output is correct
4	Correct	26 ms	5008 KB	Output is correct
5	Correct	26 ms	3444 KB	Output is correct
6	Correct	35 ms	5360 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	299 ms	155656 KB	Output is correct
9	Correct	348 ms	147592 KB	Output is correct
10	Correct	1352 ms	155532 KB	Output is correct
11	Correct	876 ms	150152 KB	Output is correct
12	Correct	519 ms	194324 KB	Output is correct
13	Correct	526 ms	197080 KB	Output is correct
14	Correct	75 ms	7084 KB	Output is correct
15	Correct	478 ms	118996 KB	Output is correct
16	Correct	379 ms	100628 KB	Output is correct
17	Correct	330 ms	95496 KB	Output is correct
18	Correct	31 ms	5360 KB	Output is correct
19	Correct	25 ms	3444 KB	Output is correct
20	Correct	35 ms	5384 KB	Output is correct
21	Correct	26 ms	5008 KB	Output is correct
22	Correct	26 ms	3444 KB	Output is correct
23	Correct	35 ms	5360 KB	Output is correct
24	Correct	257 ms	132872 KB	Output is correct
25	Correct	252 ms	134760 KB	Output is correct
26	Correct	222 ms	130492 KB	Output is correct
27	Correct	541 ms	131308 KB	Output is correct
28	Correct	168 ms	31100 KB	Output is correct
29	Correct	97 ms	12664 KB	Output is correct