Submission #373165

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

class Trie{
public:
    vector <int> preordine;
    struct Node{
        Node* v[4];
        int first;
        int second;
        set <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.insert(nr);
            return;
        }
        int c = s[ind] - '0';
        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 = s[ind] - '0';
        return interval(node->v[c], s, ind + 1);
    }
}pref, suf;

string transforma(string s){
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'A')
            s[i] = '0';
        if(s[i] == 'G')
            s[i] = '1';
        if(s[i] == 'C')
            s[i] = '2';
        if(s[i] == 'U')
            s[i] = '3';
    }
    return s;
}

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;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        s = transforma(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;
        a = transforma(a);
        b = transforma(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:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'pii Trie::interval(Trie::Node*&, std::string, int)':
selling_rna.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if(ind == s.size()){
      |            ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::string transforma(std::string)':
selling_rna.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i = 0; i < suf.preordine.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
# 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
# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 74868 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 58 ms 10416 KB Output is correct
2 Correct 40 ms 8672 KB Output is correct
3 Correct 51 ms 9828 KB Output is correct
4 Correct 47 ms 8680 KB Output is correct
5 Correct 40 ms 8428 KB Output is correct
6 Correct 50 ms 9708 KB Output is correct
# 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 1589 ms 74868 KB Time limit exceeded
9 Halted 0 ms 0 KB -