oj.uz

Submission #373170

# Submission time Handle Problem Language Result Execution time Memory
373170 2021-03-03T15:35:26 Z Vladth11 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 296 ms 199120 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 31);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const double eps = 0.0000000001;

vector <pii> events[100001];
int ce[NMAX];

char mp[257];
string cc;

class Trie{
public:
    vector <int> preordine;
    struct Node{
        Node* v[4];
        int first;
        int second;
        vector <int> st;
        Node(){
            for(int i = 0; i < 4; i++){
                v[i] = NULL;
            }
        }
    };
    Node* root;
    void insert(Node* &node, int ind, int nr){
        if(node == NULL)
            node = new Node();
        if(ind == cc.size()){
            node->st.push_back(nr);
            return;
        }
        int c = mp[cc[ind]];
        insert(node->v[c], ind + 1, nr);
    }
    void DFS(Node* &node){
        if(node == NULL)
            return;
        node->first = preordine.size();
        for(auto x : node->st){
            preordine.push_back(x);
        }
        for(int i = 0; i < 4; i++){
            DFS(node->v[i]);
        }
        node->second = preordine.size() - 1;
    }
    pii interval(Node* &node, int ind){
        if(node == NULL){
            return {-1, -1};
        }
        if(ind == cc.size()){
            return {node->first, node->second};
        }
        int c = mp[cc[ind]];
        return interval(node->v[c], ind + 1);
    }
}pref, suf;

int n, m;
int sol[NMAX];
int aib[NMAX];

void update(int x){
    for(int i = x; i <= n; i += i&(-i))
        aib[i]++;
}

int query(int x){
    int v = 0;
    for(int i = x; i > 0; i -= i&(-i))
        v += aib[i];
    return v;
}

void Sweep(){
    for(int i = 1; i <= n; i++){
        update(ce[pref.preordine[i - 1]]);
        for(auto x : events[i]){
            int semn = 1;
            if(x.second < 0)
                semn = -1;
            x.second = abs(x.second);
            sol[x.second] += semn * query(x.first);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    mp['A'] = 0;
    mp['G'] = 1;
    mp['C'] = 2;
    mp['U'] = 3;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        cc = s;
        pref.insert(pref.root, 0, i);
        reverse(s.begin(), s.end());
        cc = s;
        suf.insert(suf.root, 0, i);
    }
    pref.DFS(pref.root);
    suf.DFS(suf.root);
    for(int i = 0; i < suf.preordine.size(); i++){
        ce[suf.preordine[i]] = i + 1;
    }
    for(int i = 1; i <= m; i++){
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());
                cc = a;
        pii timpa = pref.interval(pref.root, 0);
        cc = b;
        pii timpb = suf.interval(suf.root, 0);
        int x1 = timpa.first + 1;
        int x2 = timpa.second + 1;
        int y1 = timpb.first + 1;
        int y2 = timpb.second + 1;
        if(x1 == 0 || y1 == 0){
            sol[i] = 0;
            continue;
        }
        events[x1 - 1].push_back({y1 - 1, i});
        events[x1 - 1].push_back({y2, -i});
        events[x2].push_back({y1 - 1, -i});
        events[x2].push_back({y2, i});
    }
    Sweep();
    for(int i = 1; i <= m; i++){
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message

selling_rna.cpp: In member function 'void Trie::insert(Trie::Node*&, int, int)':
selling_rna.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(ind == cc.size()){
      |            ~~~~^~~~~~~~~~~~
selling_rna.cpp:49:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |         int c = mp[cc[ind]];
      |                           ^
selling_rna.cpp: In member function 'pii Trie::interval(Trie::Node*&, int)':
selling_rna.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(ind == cc.size()){
      |            ~~~~^~~~~~~~~~~~
selling_rna.cpp:71:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |         int c = mp[cc[ind]];
      |                           ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i = 0; i < suf.preordine.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 160628 KB Output is correct
2 Correct 247 ms 153468 KB Output is correct
3 Correct 244 ms 159468 KB Output is correct
4 Correct 238 ms 152044 KB Output is correct
5 Correct 295 ms 196332 KB Output is correct
6 Correct 296 ms 199120 KB Output is correct
7 Correct 51 ms 9068 KB Output is correct
8 Correct 218 ms 121068 KB Output is correct
9 Correct 195 ms 103020 KB Output is correct
10 Correct 167 ms 97772 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6556 KB Output is correct
2 Correct 28 ms 5736 KB Output is correct
3 Correct 29 ms 6388 KB Output is correct
4 Correct 21 ms 5296 KB Output is correct
5 Correct 22 ms 5612 KB Output is correct
6 Correct 28 ms 5896 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 245 ms 160628 KB Output is correct
9 Correct 247 ms 153468 KB Output is correct
10 Correct 244 ms 159468 KB Output is correct
11 Correct 238 ms 152044 KB Output is correct
12 Correct 295 ms 196332 KB Output is correct
13 Correct 296 ms 199120 KB Output is correct
14 Correct 51 ms 9068 KB Output is correct
15 Correct 218 ms 121068 KB Output is correct
16 Correct 195 ms 103020 KB Output is correct
17 Correct 167 ms 97772 KB Output is correct
18 Correct 30 ms 6556 KB Output is correct
19 Correct 28 ms 5736 KB Output is correct
20 Correct 29 ms 6388 KB Output is correct
21 Correct 21 ms 5296 KB Output is correct
22 Correct 22 ms 5612 KB Output is correct
23 Correct 28 ms 5896 KB Output is correct
24 Correct 244 ms 134508 KB Output is correct
25 Correct 250 ms 136300 KB Output is correct
26 Correct 219 ms 132352 KB Output is correct
27 Correct 222 ms 132460 KB Output is correct
28 Correct 148 ms 32164 KB Output is correct
29 Correct 81 ms 13224 KB Output is correct