oj.uz

Submission #373167

# Submission time Handle Problem Language Result Execution time Memory
373167 2021-03-03T15:19:29 Z Vladth11 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 59660 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];

unordered_map <char, int> mp;

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, string s, int ind, int nr){
        if(node == NULL)
            node = new Node();
        if(ind == s.size()){
            node->st.push_back(nr);
            return;
        }
        int c = mp[s[ind]];
        insert(node->v[c], s, 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, string s, int ind){
        if(node == NULL){
            return {-1, -1};
        }
        if(ind == s.size()){
            return {node->first, node->second};
        }
        int c = mp[s[ind]];
        return interval(node->v[c], s, 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;
        pref.insert(pref.root, s, 0, i);
        reverse(s.begin(), s.end());
        suf.insert(suf.root, s, 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());
        pii timpa = pref.interval(pref.root, a, 0);
        pii timpb = suf.interval(suf.root, b, 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*&, std::string, int, int)':
selling_rna.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'pii Trie::interval(Trie::Node*&, std::string, int)':
selling_rna.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     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 2668 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 2668 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 2668 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 59660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6556 KB Output is correct
2 Correct 31 ms 5736 KB Output is correct
3 Correct 36 ms 6388 KB Output is correct
4 Correct 30 ms 5296 KB Output is correct
5 Correct 30 ms 5484 KB Output is correct
6 Correct 36 ms 5896 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 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 2668 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 2668 KB Output is correct
8 Execution timed out 1582 ms 59660 KB Time limit exceeded
9 Halted 0 ms 0 KB -