oj.uz

답안 #109198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109198 2019-05-05T12:22:58 Z popovicirobert Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1352 ms 197080 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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